You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

在一个无穷的数轴上，站着$n$个小朋友，第$i$个小朋友放在数轴位置$x_i$, 现在我们要从$n$个小朋友里面选出$p$个小朋友，但是你希望选出的$p$个小朋友互相之间的最小间距尽可能的大。

注意第$i$个小朋友和第$j$个小朋友之间的间距为$|x_i - x_j|$

Format

Input

第一行两个整数$n$和$p$

接下来$n$个空格隔开的整数 表示 $x_1, x_2, x_3 \dots, x_n$

Output

输出一个整数表示答案

Samples

样例输入

5 3
3 2 1 4 5

样例输出

2

样例解释

你可以选出3个小朋友他们分别在数轴的$3, 1, 5$ 处，则互相之间的最小间距为2.

Limitation

$30\%$ 的数据，$n \leq 12$

$60\%$ 的数据，$n \leq 500$

$100\%$ 的数据，$n \leq 300000$

$2 \leq k \leq n$

$-10^9 \leq x_i \leq 10^9$

1s, 256MiB for each test case.