2017 Fall Waterloo Local ACM Contest, Problem C

Vera has $N$ integers $a_1,\dots ,a_N$. A margin is a non-negative integer $L$ such that it is possible to choose $N$ integers $x_1,\dots ,x_N$ such that for all $i$, $1\le i\le N$, the interval $[x_i,x_i+L]$ contains at least $K$ of Vera's integers and also contains $a_i$.

Compute the minimum possible margin.

Input

Line $1$ contains integers $N$ and $K$ $(1\le K\le N\le 2\times {10}^5)$.

Line $2$ contains $N$ integers, $a_1,\dots ,a_N$ $(-{10}^9\le a_i\le {10}^9)$.

Output

Print one line with one integer, the minimum possible margin.

Sample Input

5 3
1 -2 10 5 4

Sample Output

6

Note

For the first example, one possible solution is to choose $x_1=-1,x_2=-2,x_3=4,x_4=0,x_5=0$, which is illustrated below.