Bessie zaprojektowała grę wideo, którą uważa za kolejny wielki hit: „Angry Cows”. Jej zdaniem całkowicie oryginalny pomysł polega na strzelaniu krowami z procy w jednowymiarową scenę z belami siana na osi liczbowej. Siła lądowania detonuje pobliskie bele. Celem jest zdetonowanie wszystkich za pomocą krów.

$N$ bel leży w różnych całkowitych pozycjach $x_1, x_2, \ldots, x_N$. Krowa wystrzelona z mocą $R$ i lądująca w $x$ powoduje wybuch o promieniu $R$, niszczący wszystkie bele w $x-R \ldots x+R$.

Dostępne są $K$ krowy, każda o tej samej mocy $R$. Wyznacz najmniejsze całkowite $R$ pozwalające tym $K$ krowom zdetonować wszystkie bele.

Wejście

Pierwszy wiersz zawiera $N$ ($1 \leq N \leq 50,000$) i $K$ ($1 \leq K \leq 10$). Pozostałe $N$ wierszy zawiera całkowite $x_1 \ldots x_N$, każda w $0 \ldots 1,000,000,000$.

Wyjście

Wypisz minimalną moc $R$ wystrzelenia każdej krowy, aby zdetonować wszystkie bele.

Przykład

Wejście 1

7 2
20
25
18
8
10
3
1

Wyjście 1

5

Autor zadania: Brian Dean