Les $N$ vaches de Farmer John occupent des positions distinctes $(x_1, y_1) \ldots (x_n, y_n)$ sur sa ferme en deux dimensions ($1 \leq N \leq 100,000$, et les $x_i$ et $y_i$ sont des entiers positifs impairs d'au plus $1,000,000$). FJ veut diviser son terrain par une longue clôture, considérée comme infinie, orientée nord-sud d'équation $x=a$. L'entier $a$ sera pair, pour ne traverser aucune vache. Il veut aussi une longue clôture, considérée comme infinie, orientée est-ouest d'équation $y=b$, avec $b$ entier pair. Elles se croisent en $(a,b)$ et divisent le terrain en quatre régions.

FJ veut choisir $a$ et $b$ pour que les vaches soient raisonnablement « équilibrées » entre les quatre régions, sans région trop peuplée. Soit $M$ le plus grand nombre de vaches dans une région. Il veut rendre $M$ aussi petit que possible. Déterminez cette plus petite valeur possible.

Entrée

La première ligne contient un entier $N$. Les $N$ lignes suivantes donnent chacune la position d'une vache : ses coordonnées $x$ et $y$.

Sortie

Affichez la plus petite valeur de $M$ obtenue en plaçant les clôtures de façon optimale.

Exemples

Entrée 1

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

Sortie 1

2

Auteur du problème : Brian Dean