Description

Farmer John has $N$ cows ($1 \leq N \leq 1000$) scattered across his farm. The farm is an infinite 2D plane, and the $i$-th cow is located at $(x_i, y_i)$ (it is guaranteed that $x_i$ and $y_i$ are positive odd integers, and $x_i, y_i \leq 10^6$). No two cows are at the same position.

FJ wants to build a vertical fence with equation $x = a$, and a horizontal fence with equation $y = b$. To ensure the fences do not pass through any cow, both $a$ and $b$ must be even. It is easy to see that these two fences intersect at $(a, b)$, partitioning the farm into four regions.

FJ wants the number 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 possible value of $M$.

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

2

Hint

Translated by ChatGPT 5