Farmer Johns $N$ Kühe stehen an verschiedenen Positionen $(x_1, y_1) \ldots (x_n, y_n)$ auf seiner zweidimensionalen Farm ($1 \leq N \leq 100,000$; $x_i$ und $y_i$ sind positive ungerade ganze Zahlen höchstens $1,000,000$). FJ will das Feld mit einem langen, praktisch unendlichen Zaun in Nord-Süd-Richtung mit Gleichung $x=a$ teilen. Die ganze Zahl $a$ wird gerade sein, damit er keine Kuhposition durchquert. Außerdem will er einen langen, praktisch unendlichen Zaun in Ost-West-Richtung $y=b$ errichten, wobei $b$ eine gerade ganze Zahl ist. Beide kreuzen sich bei $(a,b)$ und teilen das Feld in vier Bereiche.

FJ möchte $a$ und $b$ so wählen, dass die Kühe in den vier Bereichen einigermaßen „ausgewogen“ verteilt sind und keiner zu viele enthält. Sei $M$ die größte Kuhanzahl in einem Bereich. Er möchte $M$ möglichst klein machen. Bestimme diesen kleinsten möglichen Wert.

Eingabe

Die erste Zeile enthält eine ganze Zahl $N$. Die nächsten $N$ Zeilen geben jeweils die Position einer Kuh als $x$- und $y$-Koordinate an.

Ausgabe

Gib den kleinsten möglichen Wert von $M$ bei optimaler Zaunplatzierung aus.

Beispiele

Eingabe 1

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

Ausgabe 1

2

Aufgabenautor: Brian Dean