Archiwum zadań programistycznych WWSI

Michał posiada sad, w którym rośnie n jabłoni. Nasz bohater jest również ojcem czwórki dzieci, którym kiedyś ma zamiar przekazać swój majątek. Michał nie chce, aby jego potomstwo sprzeczało się o podział majątku, dlatego postanowił samemu podzielić sad na cztery części. Sadownik wypisał współrzędne x,y każdej z n jabłoni. Teraz ma zamiar poprowadzić dwie proste, jedną równoległą do osi odciętych, drugą równoległą do osi rzędnych, które to podzielą jego sad na cztery części. Proste nie mogą przechodzić przez punkty, w których rosną jabłonie. Nasz bohater chce, aby podział był możliwie jak najbardziej sprawiedliwy. Konkretnie rzecz ujmując zależy mu na tym, aby różnica pomiędzy częścią zawierającą najwiekszą liczbę jabłoni, a częścią zawierającą najmniejszą liczbę jabłoni była jak najmniejsza.

Twoim zadaniem jest wyznaczenie szukanej różnicy.

Wejście

W pierwszej linii znajduje się jedna liczba całkowita n ∈ [1;1000] określająca liczbę jabłoni rosnących w sadzie. W kolejnych n liniach znajdują się po dwie liczby całkowite x ∈ [0;10⁹] i y ∈ [0;10⁹] określające współrzędne jabłoni.

Wyjście

Na wyjściu należy wypisać szukaną różnicę.

Przykład

Wejście:

5
1 1
3 1
3 3
1 4
1 5

Wyjście:

1

Wyjaśnienie do przykładu:

Nasz bohater może poprowadzić prostą równoległą do osi odciętych przez punkt (0,2), zaś prostą równoległą do osi rzędnych przez punkt (2,0). W ten sposób uzyska cztery części o liczbie jabłoni: 1, 1, 1, 2, a zatem różnica pomiędzy najliczniejszą, a najmniej liczną częścią wynosi 1.