Żuki

Limit pamięci: 32 MB

Jaś bada zachowanie żuków żyjących na dużej, kwadratowej łące. Zauważył już, że każdy żuczek spędza życie spacerując po odcinku między dwoma upatrzonymi przez siebie punktami. Jaś chce złapać co najmniej żuków do dalszych eksperymentów. W tym celu dokładnie zbadał, którędy one spacerują. Teraz planuje zrobić kwadratowe ogrodzenie i położyć je na łące tak, żeby w środku znalazło się co najmniej żuków (żuk przygnieciony przez ogrodzenie również liczy się jako złapany). Dodatkowo (dla ułatwienia polowania) ogrodzenie zostanie położone tak, żeby jego boki były równoległe do brzegów łąki.

Teraz pozostaje obliczyć rozmiar najmniejszego takiego ogrodzenia, które można tak położyć na łące, żeby złapało się do niego co najmniej żuków, niezależnie od tego, gdzie się one aktualnie będą znajdowały na swojej trasie.

Zadanie

Napisz program, który:

• wczyta opis tras żuków oraz liczbę potrzebnych żuków,
• wyznaczy bok najmniejszego kwadratowego ogrodzenia, które wystarczy Jasiowi,
• wypisze wynik.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i , , oddzielone pojedynczym odstępem. Liczba to liczba żuków na łące, a to liczba żuków potrzebnych Jasiowi.

W kolejnych wierszach opisane są trasy wędrówek żuków. W wierszu o numerze , , znajdują się cztery liczby całkowite , , oddzielone pojedynczymi odstępami, opisujące trasę jednego żuka. Współrzędne końców tej trasy to i (Współrzędne oznaczają punkt odległy o od zachodniego i o od południowego brzegu łąki).

Wyjście

W jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita: długość boku najmniejszego ogrodzenia spełniającego wymagania Jasia.

Przykład

Dla danych wejściowych:

4 2
1 0 3 1
0 2 1 4
4 2 2 3
2 1 1 2

poprawną odpowiedzią jest:

2