Description

Mirko 最新的数学作业非常难！给定一个长度为 $N$ 的整数序列 $V$，你需要从中恰好移除 $K$ 个数。设 $M$ 为剩下所有数中任意两数的最大差值，$m$ 为最小差值。请你选择要移除的 $K$ 个数，使得 $M + m$ 的值尽可能小。Mirko 数学不太好，所以他请求你帮忙！

Input Format

第一行输入两个正整数 $N$（$3 \leq N \leq 1\,000\,000$）和 $K$（$1 \leq K \leq N - 2$）。

第二行输入 $N$ 个用空格分隔的整数，表示序列 $V$（$-5\,000\,000 \leq V_i \leq 5\,000\,000$）。

Output Format

输出一行，表示最小可能的 $M + m$。

5 2
-3 -2 3 8 6

7

6 2
-5 8 10 1 13 -1

13

6 3
10 2 8 17 2 17

6

Hint

翻译由 ChatGPT-4.1 完成。