Background

有一些可爆燃的猪堆分布在一条数轴的不同坐标，玩家用弹弓把 小鸟发射到数轴上。小鸟砸到数轴上的冲击波会引发附近的猪堆燃 爆，并有可能引起附近的猪堆连环燃爆。游戏的目标是玩家用一些小 鸟燃爆所有的猪堆。

Description

有 N 个猪堆在数轴的不同位置，坐标为 x1,x2,….,xn。如果玩 家把小鸟发射到坐标是 x，能量是 R，就会引爆半径 R 以内的的猪堆， 即坐标范围[x-R, x+R]的草堆都会燃爆。
现在有 K 只小鸟，每只小鸟的能量都是 R，请计算如果要引爆所 有的猪堆，最小的 R 是多少？

Format!

Input

第一行：2 个整数 N 和 K。
以下 N 行,每行一个整数：x1, x2 ,…,xn。

Output

最小可能的 R。

Sample 1

Input

7 2
20
25
18
8
10
3
1

Output

5

Source

比赛用题库