Коровы Farmer John числом $N$ стоят в различных точках $(x_1, y_1) \ldots (x_n, y_n)$ двумерной фермы ($1 \leq N \leq 100,000$, а $x_i$ и $y_i$ — положительные нечётные целые не больше $1,000,000$). FJ хочет разделить поле длинным, фактически бесконечным забором с севера на юг $x=a$. Число $a$ будет чётным целым, поэтому забор не пройдёт через корову. Он также хочет длинный, фактически бесконечный забор с востока на запад $y=b$, где $b$ — чётное целое. Они пересекаются в $(a,b)$ и делят поле на четыре области.

FJ хочет выбрать $a$ и $b$, чтобы число коров в четырёх областях было разумно «сбалансировано», без слишком большого скопления в одной. Пусть $M$ — максимальное число коров в одной из четырёх областей. Он хочет минимизировать $M$. Помогите определить его наименьшее возможное значение.

Входные данные

Первая строка содержит одно целое $N$. Следующие $N$ строк содержат по позиции коровы: её координаты $x$ и $y$.

Выходные данные

Выведите наименьшее возможное значение $M$ при оптимальном расположении заборов.

Примеры

Входные данные 1

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

Выходные данные 1

2

Автор задачи: Brian Dean