贝蒂熊设计了一个新型的破坏游戏：愤怒小熊。游戏的前提是玩家用弹弓将小熊射入一维场景中，场景由一条数字线上的一组蜂蜜罐组成。每只小熊着陆时产生足够的力量，使附近的蜂蜜罐爆炸。

游戏目标是使用一组小熊爆破场景中的所有蜂蜜罐。

数字线上有 N 个蜂蜜罐，位于不同的整数位置 x_1,x_2,\dots,x_N 。

如果一只小熊以 R 的力量降落在位置 x，这将产生一个“半径 R”的爆炸，摧毁范围 [x-R,x+R] 内的所有蜂蜜罐。

共有 K 只小熊可以射击，每只小熊具有相同的力量 R。请确定 R 的最小整数值，使得可以最多使用 K 只小熊破坏场景中的每个蜂蜜罐。

输入的第一行包含 N 和 K 。

其余 N 整数 x_1,x_2,\dots,x_N 。

请输出每只小熊必须发射的最小力量 R，以破坏所有蜂蜜罐。

样例 1 说明

对于这个样例，为了破坏所有的蜂蜜罐，需要使用 2 只小熊破坏它们。我们可以选择在 5 和 20 的位置降落小熊，而 R=5 是这两个位置可以覆盖所有蜂蜜罐的最小值。

第 1 只小熊可以摧毁 [5-5,5+5] 范围内的蜂蜜罐，第 2 只小熊可以摧毁 [20-5,20+5] 范围内的蜂蜜罐。

这样每只小熊的爆炸范围都可以覆盖所有的蜂蜜罐。因此输出为 5。

数据范围

对于 50\% 的数据，1 \le N \le 1000。

对于 100\% 的数据， 1 \leq N \leq 5\times 10^4， 1 \leq K \leq 10 ，0 \le x_i \le 10^9。

东方博宜OJ

月赛二分答案