Bessie создала видеоигру «Angry Cows», которая, по её мнению, станет новым хитом. Считая идею полностью оригинальной, она предлагает стрелять коровами из рогатки в одномерную сцену с тюками сена на числовой прямой. Сила приземления взрывает близкие тюки. Цель — с помощью коров взорвать все тюки.

$N$ тюков стоят в различных целых позициях $x_1, x_2, \ldots, x_N$. Корова, запущенная с силой $R$ и приземлившаяся в $x$, вызывает взрыв радиуса $R$, уничтожающий все тюки в диапазоне $x-R \ldots x+R$.

Доступно $K$ коров, все запускаются с одинаковой силой $R$. Найдите минимальное целое $R$, позволяющее этими $K$ коровами взорвать все тюки.

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

Первая строка содержит $N$ ($1 \leq N \leq 50,000$) и $K$ ($1 \leq K \leq 10$). Оставшиеся $N$ строк содержат целые $x_1 \ldots x_N$, каждое в диапазоне $0 \ldots 1,000,000,000$.

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

Выведите минимальную силу $R$ запуска каждой коровы, чтобы взорвать все тюки.

Примеры

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

7 2
20
25
18
8
10
3
1

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

5

Автор задачи: Brian Dean