Problem A
Strumpmatchning 2

Arash har nu kommit hem från onsite-finalen i Linköping och är tillbaka i vardagen. Nu har han precis kommit hem från ett tvättstugebesök och ska återigen matcha strumpor. När han nu sitter där med sina $N$ strumpor så känner han att han bara behöver $K$ par strumpor, resten kan få förbli osorterade. Det är alltså okej om $N-2K$ strumpor förblir omatchade, tänker Arash.

Som i uppgiften strumpmatchning så har varje strumpa en färg $F_ i$. Två strumpor $i$ och $j$ kan paras ihop om skillnaden i färg strikt understiger heltalet $D$ d.v.s. $|F_{i} - F_{j}|<D$. Men istället för att hjälpa Arash matcha så många strumpor som möjligt så ska du hjälpa honom att hitta det minsta möjliga $D$ så att han kan matcha minst $K$ strumppar!

Indata

Indata består av en rad med de två heltalen $N$ och $K$ ($2 \le N \le 50\, 000$, $2 \le 2K \le N$). Därefter följer en rad med $N$ heltal: $F_1, F_2, \dots , F_ N$. Talen $F_ i$ ligger mellan $1$ och $1\, 000\, 000\, 000\, 000\, 000$ (inklusive).

Utdata

Du ska skriva ut ett enda heltal: den minimala differens $D$ som gör att Arash kan matcha minst $K$ strumppar med varandra.

Delpoäng

I det här problemet kan du samla en del av poängen utan att lösa problemet fullständigt.

• För $40$ poäng så kommer $N$ vara maximalt $200$ och varje färg maximalt $5\, 000$.

• För ytterligare $30$ poäng så kommer $N$ vara maximalt $1\, 000$.

5 2
3 8 1 5 9

3

4 1
100 101 102 103

2

10 4
81 92 42 45 62 5 4 85 73 22

9

2 1
1000000000000 5000000000000

4000000000001