Choosing Numbers

You are given a sequence of numbers. Consider the differences between every pair of its elements. Let $M$ be the largest such difference and $m$ be the smallest. (Equivalently, $M$ is the maximum value minus the minimum value, and $m$ is the smallest gap between two adjacent values once the elements are sorted.)

A sequence $V$ of size $N$ is given. Write a program that removes exactly $K$ of its numbers so that, for the remaining $N-K$ numbers, the value $M+m$ is as small as possible.

The first line contains two integers $N$ ($3 \le N \le 10^6$) and $K$ ($1 \le K \le N-2$).

The second line contains the $N$ elements of $V$, separated by spaces ($-5 \times 10^6 \le V_i \le 5 \times 10^6$).

Print the smallest possible value of $M+m$ on the first line.