该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小明有$n$瓶生理盐水，由于浓度不太一样， 以及混进来了一些奇怪的东西，第$i$瓶生理盐水的酸碱度是$a_i$。

小明觉得$n$个瓶子太多了，于是他决定把这$n$瓶盐水重新灌装进$k$个瓶子中。

把若干瓶盐水混到一起的前提条件是：每一瓶盐水的酸碱度是一样的。

这显然太困难了，所以小明准备去哆啦A梦的杂货铺购买道具“酸碱度修改器”。

“酸碱度修改器”有一个属性值$m$，当你使用它在某一瓶盐水上的时候，可以把这瓶盐水的酸碱度增加/减少最多$m$。比如你有一个属性为$3$的“酸碱度修改器”，那么你可以把原来酸碱度为$4$的生理盐水的酸碱度修改为$1,2,3,4,5,6,7$中的任何一个值。

“酸碱度修改器”可以重复使用。但是，对于每一瓶生理盐水来说只能使用一次。

属性值$m$越大的“酸碱度修改器”越贵，因此，小明决定购买$m$尽量小的，请帮助小明算一算，他最少要买属性为多少的“酸碱度修改器”。

输入格式

第一行输入$n,k$。

接下来一行输入$n$个正整数表示$a_i$。

输出格式

一个数字表示答案。

样例输入 #1

4 2
1 3 5 7

样例输出 #1

1

样例解释 #1

把$1$和$3$修改成$2$，把$5$和$7$修改成$6$，只需要属性为$1$的修改器即可。

样例输入 #2

4 1
1 3 5 7

样例输出 #2

3

数据范围

对于30%的数据：$n\leq 20$。

对于50%的数据：$n\leq 500$。

对于另外20%的数据：$k=2$。

对于100%的数据：$1\leq k\leq n\leq 10^5,1\leq a_i\leq 10^9$。