Bessie ha progettato un videogioco che pensa diventerà il prossimo grande successo: «Angry Cows». L'idea, che crede completamente originale, è lanciare mucche con una fionda in una scena unidimensionale con balle di fieno in vari punti della retta numerica. La forza di ogni atterraggio fa esplodere le balle vicine. L'obiettivo è farle esplodere tutte usando delle mucche.

Ci sono $N$ balle in posizioni intere distinte $x_1, x_2, \ldots, x_N$. Una mucca lanciata con potenza $R$ che atterra in $x$ provoca un'esplosione di raggio $R$, distruggendo tutte le balle in $x-R \ldots x+R$.

Sono disponibili $K$ mucche, tutte con la stessa potenza $R$. Trova il minimo intero $R$ che permette a queste $K$ mucche di far esplodere tutte le balle.

Input

La prima riga contiene $N$ ($1 \leq N \leq 50,000$) e $K$ ($1 \leq K \leq 10$). Le restanti $N$ contengono gli interi $x_1 \ldots x_N$, ciascuno in $0 \ldots 1,000,000,000$.

Output

Stampa la minima potenza $R$ di lancio di ogni mucca per far esplodere tutte le balle.

Esempi

Input 1

7 2
20
25
18
8
10
3
1

Output 1

5

Autore del problema: Brian Dean