Description

Farmer John has $N$ cows ($1 \leq N \leq 10^5$) scattered across the farm. The farm is an infinitely large 2D plane. The position of the $i$-th cow is $(x_i, y_i)$ (it is guaranteed that both $x_i$ and $y_i$ are positive odd numbers, and $x_i, y_i \leq 10^6$), and no two cows are at the same location.

FJ wants to build a vertical fence with equation $x = a$, and also a horizontal fence with equation $y = b$. To prevent the fences from passing through any cows, both $a$ and $b$ must be even numbers. It is easy to see that these two fences intersect at $(a, b)$, dividing the farm into four regions.

FJ wants the numbers of cows in the four regions to be as balanced as possible, avoiding the situation where one region has many cows while another has few. Let $M$ be the maximum number of cows among the four regions. Please help FJ find the minimum possible value of $M$.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain two integers $x_i, y_i$, describing the position of the $i$-th cow.

Output Format

Output the minimum value of $M$.

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

2

Hint

Translated by ChatGPT 5