Bessie a conçu un jeu vidéo qu'elle croit promis au succès : « Angry Cows ». Son idée, qu'elle pense entièrement originale, consiste à lancer des vaches avec un lance-pierre dans une scène unidimensionnelle où des balles de foin occupent divers points d'une droite numérique. Chaque atterrissage fait exploser les balles proches. Le but est de faire exploser toutes les balles à l'aide des vaches.

$N$ balles occupent des positions entières distinctes $x_1, x_2, \ldots, x_N$. Une vache lancée avec une puissance $R$ et atterrissant en $x$ provoque une explosion de rayon $R$ qui détruit toutes les balles dans $x-R \ldots x+R$.

$K$ vaches sont disponibles, toutes de même puissance $R$. Trouvez la plus petite valeur entière de $R$ permettant à ces $K$ vaches de faire exploser toutes les balles.

Entrée

La première ligne contient $N$ ($1 \leq N \leq 50,000$) et $K$ ($1 \leq K \leq 10$). Les $N$ restantes contiennent les entiers $x_1 \ldots x_N$, chacun dans $0 \ldots 1,000,000,000$.

Sortie

Affichez la puissance minimale $R$ de chaque vache permettant de faire exploser toutes les balles.

Exemples

Entrée 1

7 2
20
25
18
8
10
3
1

Sortie 1

5

Auteur du problème : Brian Dean