Description

Bessie designed a new game: Angry Cows. In this game, the player launches cows, and each cow explodes on landing, detonating hay bales within a certain range. The goal of the game is to use a set of cows to detonate all the hay bales.

There are $N$ hay bales located at distinct positions on a number line. The position of the $i$-th hay bale is $x_i$. If a cow with power $R$ lands at position $x$, she will detonate all hay bales in the range $[x-R, x+R]$.

You can now launch $K$ cows, each with power $R$. You need to determine the minimum value of $R$ such that all hay bales can be detonated using $K$ cows.

Input Format

The first line contains two integers $N, K$ ($1 \leq N \leq 5 \times 10^4$, $1 \leq K \leq 10$).

The next $N$ lines each contain an integer $x_i$ ($0 \leq x_i \leq 10^9$).

Output Format

Output one integer, the minimum value of $R$.

7 2
20
25
18
8
10
3
1

5

Hint

Translated by ChatGPT 5