kda

League of Legends este un popular joc online ce este de cele mai multe ori mult mai plăcut dacă este jucat împreuna cu prietenii. În timpul unui meci obiectivele principale ale unui jucător sunt să omoare cât mai mulți inamici (Kill-uri), să fie omorât de cât mai puține ori (Death-uri) și să își ajute coechipierii în a ucide inamici (Assist-uri). Astfel, o metodă comună prin care nivelul unui jucător este aproximat este KDA-ul (Kills, Deaths, Assists), un număr întreg ce combină cele trei obiective ale unui jucător. KDA-ul este calculat automat așa că metoda de calcul nu este una de interes.

Gigel are $N$ prieteni, iar pentru fiecare el cunoaște KDA-ul. Deoarece toți prietenii lui Gigel sunt foarte buni KDA-ul lor este un număr întreg pozitiv. Pentru un turneu de LoL el vrea să formeze echipe din $k$ prieteni. Pentru ca toată lumea să se distreze, obiectivul lui este să echilibreze cât mai tare echipele, astfel prietenii cu un KDA mai mare să nu fie în aceeași echipă cu prieteni cu un KDA scăzut.

Pentru a vedea cât de echilibrată este o echipă, el se gândeste să folosească un coeficient de echilibru (qE). Coeficientul de echilibru al unei echipe poate fi aflat astfel: luăm toate perechile posibile de jucători din echipă, calculăm diferența absolută între KDA-urile celor doi, iar la final coeficientul de echilibru este minimul dintre aceste diferențe calculate. O echipă este cu atât mai echilibrată cu cât qE-ul ei este mai mic.

Cerință

Dându-se o listă conținând KDA-urilor celor $N$ prieteni ai lui Gigel și mărimea unei echipe $k$, Gigel dorește să afle care este qE-ul celei mai neechilibrate echipe. Astfel el calculează qE-ul tuturor echipelor posibile ($\frac{N!}{k!(N-k)!}$ la număr) și apoi alege qE-ul maxim posibil.

Date de intrare

Pe prima linie se află numerele $N$ și $k$. Pe următoarea linie se află $N$ numere pozitive întregi, reprezentând KDA-urile celor $N$ prieteni.

Date de ieșire

Se va afișa un singur număr întreg reprezentând qE-ul maxim posibil al unei echipe formate din $k$ prieteni.

Restricții și precizări

• $1 \leq k \leq N \leq 100 \ 000$;
• KDA-ul unui jucător este un număr natural mai mic sau egal decât 10^5;
• Pentru $10$ puncte, $k = 2$;
• Pentru $20$ de puncte, $1 \leq N \leq 35$.

Exemplu

stdin

5 3
1 3 4 6 7

stdout

3

Explicație

Echipele posibile sunt:

• $\{1, 3, 4\}$ cu qE $1$;
• $\{1, 3, 6\}$ cu qE $2$;
• $\{1, 3, 7\}$ cu qE $2$;
• $\{1, 4, 6\}$ cu qE $2$;
• $\{1, 4, 7\}$ cu qE $3$;
• $\{1, 6, 7\}$ cu qE $1$;
• $\{3, 4, 6\}$ cu qE $1$;
• $\{3, 4, 7\}$ cu qE $1$;
• $\{3, 6, 7\}$ cu qE $1$;
• $\{4, 6, 7\}$ cu qE $1$.

Deci qE-ul maxim posibil este $3$, obținut formând echipa $\{1, 4, 7\}$.