Бесси создала новую игру. Игрок стреляет коровами на одномерную сцену, состоящую из множества стогов сена расположенных в различных точках на числовой прямой. Каждая корова приземляется с силой достаточной, чтобы разрушить ближайшие к точке приземления стоги. Цель - использовать множество коров так, чтобы разрушить все стоги сена.

Имеется n стогов сена расположенных в целочисленных позициях x1, x2, ... , xn на числовой прямой. Если корова приземляется с энергией r в позиции x, это вызывает взрыв "радиуса r", разрушающий все стоги сена в диапазоне x − r ... x + r.

Всего имеется k коров для выстрелов, каждая с одной и той же энергией r. Определите минимальную целую величину r такую, что возможно используя эти k коров разрушить все стоги сена на сцене.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 50000) и k (1 ≤ k ≤ 10). Каждая из оставшихся n строк содержит целые числа x1 ... xn (каждое в интервале 0 ... 109).

Выходные данные

Выведите минимальную энергию r, с которой должна приземлиться каждая корова, для того чтобы разрушить все стоги сена.