Problem description


Kwadrat z punktami
(F)
Limit pamięci: 256 MB
Limit czasu: 8.00 s

Jasio, jak to zwykle bywa na tym turnieju, ma problem. Ma zbiór N punktów na płaszczyźnie. Chciałby przykryć co najmniej K spośród nich kwadratem o jak najmniejszym boku. Dla uproszczenia, żeby w zadaniu nie było zbyt dużo prawdziwej geometrii, Jasio akceptuje jedynie kwadraty o bokach równoległych do osi układu współrzędnych. Zakładamy również, że jeżeli kwadrat dotyka jakiegoś punktu, to go przykrywa. Czy pomożesz mu w tym zadaniu?

Napisz program, który: wczyta współrzędne punktów oraz wartość K, wyznaczy optymalny kwadrat przykrywający co najmniej K spośród punktów podanych na wejściu i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz K, oddzielone pojedynczym odstępem. Oznaczają one kolejno: liczbę punktów na płaszczyźnie oraz minimalną liczbę punktów, które należy przykryć.

W kolejnych N wierszach znajduje się opis kolejnych punktów. Opis każdego punktu składa się z dwóch liczb naturalnych xi oraz yi, oddzielonych pojedynczym odstępem. Oznaczają one, że i-ty punkt znajduje się na pozycji (xi,yi).

Możesz założyć, że współrzędne wszystkich punktów są parami różne.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalna długość boku kwadratu, który (przy swoim optymalnym ułożeniu, zgodnie z warunkami zadania) może przykryć co najmniej K punktów podanych na wejściu.

Ograniczenia

1 ≤ K ≤ N ≤ 2 000, 1 ≤ xi, yi ≤ 109.

Przykład

Wejście Wyjście
11 6
1 1
3 4
4 3
6 6
1 6
6 3
2 4
4 1
4 5
5 2
5 4
3