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 puncte5.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 puncte5.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 ≤ xi ≤ 5 000 şi 1 ≤ yi ≤ 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.
Exemple
puncte5.in
puncte5.out
Explicaţii
7 4
3 2
1 1
1 2
4 3
3 4
6 6
5 2
2
Pătratul cu colţul stânga jos în punctul (3,2) şi latura 2 conţine 4 puncte şi anume: (3,2), (4,3), (3,4) şi (5,2)