Le $N$ mucche di Farmer John occupano posizioni distinte $(x_1, y_1) \ldots (x_n, y_n)$ nella fattoria bidimensionale ($1 \leq N \leq 100,000$, e $x_i$, $y_i$ sono interi positivi dispari non maggiori di $1,000,000$). FJ vuole dividere il terreno con una lunga recinzione, di fatto infinita, orientata nord-sud, di equazione $x=a$. L'intero $a$ sarà pari, evitando di passare per qualsiasi mucca. Vuole anche una lunga recinzione, di fatto infinita, orientata est-ovest, $y=b$, con $b$ intero pari. Si intersecano in $(a,b)$ e dividono il terreno in quattro regioni.

FJ vuole scegliere $a$ e $b$ affinché le mucche siano ragionevolmente «bilanciate» tra le quattro regioni, senza che nessuna ne contenga troppe. Sia $M$ il massimo numero di mucche in una regione. Vuole minimizzare $M$. Aiutalo a trovare il minimo valore possibile.

Input

La prima riga contiene un intero $N$. Le successive $N$ righe danno ciascuna la posizione di una mucca: coordinate $x$ e $y$.

Output

Stampa il minimo valore possibile di $M$ posizionando le recinzioni in modo ottimale.

Esempi

Input 1

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

Output 1

2

Autore del problema: Brian Dean