castori

Pe o câmpie întinsă oarecare sunt $C$ castori şi $N$ vizuine ce pot fi reprezentate ca puncte laticiale în plan. Castorii trebuie să îşi aleagă fiecare câte o vizuină unde poate să se ascundă în caz de pericol. Se ştie că o vizuină nu poate adăposti mai mult de un castor. Castorii doresc să îşi aleagă vizuinele astfel încât cele mai îndepărtate două vizuine din cele selectate să fie cât mai apropiate posibil.

Cerinţă

Să se selecteze $C$ dintre cele $N$ vizuine astfel încât maximul distanţelor dintre oricare două selectate să fie minim posibil. Prin distanţa între două puncte $(x_1 \ y_1)$ şi $(x_2 \ y_2)$ se va înţelege distanţa Manhattan $|x_1-x_2|+|y_1-y_2|$.

Date de intrare

Pe prima linie a fişierului de intrare castori.in se află două numere naturale $N$ şi $C$, cu semnificaţia din enunţ. Fiecare din urmatoarele $N$ linii conţine câte o pereche de numere întregi $x \ y$, reprezentând coordonatele unei vizuine.

Date de ieșire

Pe prima linie a fişierului de ieşire castori.out se va scrie distanţa cerută.

Restricții și precizări

• $2 \leq C \leq N \leq 10 \ 000$
• Coordonatele vizuinelor vor fi numere întregi din intervalul $[-10^8, +10^8]$
• Nu vor exista două vizuine în acelaşi punct

Exemplu

castori.in

5 3
2 9
-1 -5
6 -3
8 4
-2 2

castori.out

12

Explicație

Se vor selecta vizuinele $1$, $4$ şi $5$. Distanţa între oricare două va fi:

• distanţă $(1, 4) = |2-8|+|9-4| = 11$
• distanţă $(1, 5) = |2-(-2)|+|9-2| = 11$
• distanţă $(4, 5) = |8-(-2)|+|4-2| = 12$
  Oricum am selecta alte 3 vizuine, distanţa dintre cele mai îndepărtate două este mai mare decât $12$.