Choosing Numbers

Time limit1sMemory limit256 MB

Summary

Given a sequence, delete exactly K elements so that the sum of the largest gap and the smallest adjacent gap among the remaining elements is minimized.

Level: Medium7 of 10
Topics: Sorting, Sliding window, Greedy, Two pointers
Solved: No attempts yet

Problem

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.

Input

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$ ).

Output

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

Examples3

Example 1
Input
```
5 2
-3 -2 3 8 6
```
Expected output
```
7
```
Example 2
Input
```
6 2
-5 8 10 1 13 -1
```
Expected output
```
13
```
Example 3
Input
```
6 3
10 2 8 17 2 17
```
Expected output
```
6
```