Krowy Farmer John, w liczbie $N$, stoją w różnych miejscach $(x_1, y_1) \ldots (x_n, y_n)$ na dwuwymiarowej farmie ($1 \leq N \leq 100,000$, a $x_i$, $y_i$ są dodatnimi nieparzystymi liczbami całkowitymi najwyżej $1,000,000$). FJ chce podzielić pole długim, praktycznie nieskończonym płotem w kierunku północ-południe o równaniu $x=a$. Liczba całkowita $a$ będzie parzysta, aby płot nie przechodził przez żadną krowę. Chce też długi, praktycznie nieskończony płot w kierunku wschód-zachód $y=b$, gdzie $b$ jest parzystą liczbą całkowitą. Przecinają się w $(a,b)$, dzieląc pole na cztery obszary.

FJ chce wybrać $a$ i $b$, aby krowy w czterech obszarach były rozsądnie „zrównoważone”, bez zbyt licznego obszaru. Niech $M$ będzie największą liczbą krów w jednym z czterech obszarów. Chce zminimalizować $M$. Pomóż ustalić najmniejszą możliwą wartość.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $N$. Kolejne $N$ wierszy podaje pozycję jednej krowy: współrzędne $x$ i $y$.

Wyjście

Wypisz najmniejszą wartość $M$, osiągalną przy optymalnym ustawieniu płotów.

Przykład

Wejście 1

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

Wyjście 1

2

Autor zadania: Brian Dean