有\(n\)個人站在數線上，整數\(a_i\)代表第\(i\)個人的座標。

茅場愛衣在希望開發出\(n\)個品質相同的Verngear讓\(n\)個人都戴上。

品質是\(k\)的Verngear可以讓兩個相距不超過\(k\)單位的人產生連結。

不過茅場愛衣開發品質是\(k\)的Verngear需要花費他恰好\(k\)點體力。

他的目標是用最少點體力讓至少\(m\)對人產生連結。

請問茅場愛衣最少需要花多少點體力？

Input

第一行輸入兩個正整數\(n,m\)。

第二行輸入\(n\)個整數\(a_1,a_2,...,a_n\)。

\(1\le n\le 10^{5},0\le m\le \frac{n(n-1)}{2},0\le a_i\le10^9\)

保證每個人站的位置都不一樣。

Output

輸出茅場愛衣所需要花的最少體力。

註：可證明答案一定是整數。

Constraints

第 \(1\) 組測資 \(10\) 分：\(n\le 10\)。

第 \(2\) 組測資 \(10\) 分：\(n\le 100\)。

第 \(3\) 組測資 \(20\) 分：\(n\le 1000\)。

第 \(4\) 組測資 \(20\) 分：\(n\le 5000\)。

第 \(5\) 組測資 \(40\) 分：無特別限制。

Sample Input 1

5 2
1 3 10 14 39

Sample Output 1

4

Sample Input 2

4 3
1 19 29 49

Sample Output 2

20