Fișierul intrare/ieșire	puncte1.in, puncte1.out	Sursă	ONI 2012 baraj gimnaziu
Autor	Dana Lica	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	1 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Puncte1 (baraj gimnaziu)

Se consideră N puncte distincte în planul definit de sistemul cartezian XOY. Fiecare punct este definit prin două numere naturale nenule reprezentând abscisa, respectiv ordonata sa. În plan putem trasa oriunde un pătrat cu laturile paralele cu axele sistemului, având lungimea laturii un număr natural nenul.

Cerință

Scrieți un program care determină lungimea minimă a laturii unui pătrat care poate fi trasat, astfel încât acesta să includă cel puțin K puncte dintre cele N puncte date.

Date de intrare

Fișierul de intrare puncte1.in conține pe prima linie perechea de numere naturale N și K, reprezentând numărul de puncte din plan, respectiv numărul minim de puncte care trebuie să fie în interiorul pătratului de latură minimă. Pe următoarele N linii se află câte două numere naturale, x și y, separate printr-un spațiu, reprezentând, în această ordine, abscisa și ordonata fiecăruia dintre cele N puncte.

Date de ieșire

Fișierul de ieșire puncte1.out conține pe prima linie un număr natural nenul, ce reprezintă lungimea minimă a laturii determinate.

Restricții

• 2 ≤ N ≤ 32 000
• 2 ≤ K ≤ N
• 1 ≤ x_i ≤ 5 000 și 1 ≤ y_i ≤ 5 000, pentru orice 1 ≤ i ≤ N
• Un punct aflat pe oricare latură a pătratului, sau în oricare vârf, se consideră inclus în pătrat.

Exemplu