Bessie diseñó un videojuego que cree que será un gran éxito: «Angry Cows». La idea, que considera totalmente original, es lanzar vacas con un tirachinas a una escena unidimensional con fardos de heno en puntos de una recta numérica. La fuerza del aterrizaje detona los fardos cercanos. El objetivo es detonar todos usando unas vacas.

Hay $N$ fardos en posiciones enteras distintas $x_1, x_2, \ldots, x_N$. Una vaca lanzada con potencia $R$ que aterriza en $x$ provoca una explosión de radio $R$, destruyendo todos los fardos en $x-R \ldots x+R$.

Se dispone de $K$ vacas, todas con potencia $R$. Halla el menor entero $R$ que permite usar las $K$ vacas para detonar todos los fardos.

Entrada

La primera línea contiene $N$ ($1 \leq N \leq 50,000$) y $K$ ($1 \leq K \leq 10$). Las restantes $N$ contienen enteros $x_1 \ldots x_N$, cada uno en $0 \ldots 1,000,000,000$.

Salida

Imprime la potencia mínima $R$ de lanzamiento de cada vaca para detonar todos los fardos.

Ejemplos

Entrada 1

7 2
20
25
18
8
10
3
1

Salida 1

5

Autor del problema: Brian Dean