Ż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