Bessie criou um videojogo que considera o próximo grande êxito: «Angry Cows». A ideia, que acha totalmente original, é lançar vacas com uma fisga para um cenário unidimensional com fardos de feno em pontos da reta numérica. A força de cada aterragem detona os fardos próximos. O objetivo é detonar todos usando um conjunto de vacas.

Há $N$ fardos em posições inteiras distintas $x_1, x_2, \ldots, x_N$. Uma vaca lançada com potência $R$ que aterra em $x$ provoca uma explosão de raio $R$, destruindo todos os fardos em $x-R \ldots x+R$.

Há $K$ vacas disponíveis, todas com potência $R$. Determine o menor inteiro $R$ que permite usar estas $K$ vacas para detonar todos os fardos.

Entrada

A primeira linha contém $N$ ($1 \leq N \leq 50,000$) e $K$ ($1 \leq K \leq 10$). As $N$ restantes contêm os inteiros $x_1 \ldots x_N$, cada um em $0 \ldots 1,000,000,000$.

Saída

Imprima a potência mínima $R$ de lançamento de cada vaca para detonar todos os fardos.

Exemplos

Entrada 1

7 2
20
25
18
8
10
3
1

Saída 1

5

Autor do problema: Brian Dean