Load Balancing

Time limit2sMemory limit512 MB

Summary

Place one vertical and one horizontal fence between the odd-coordinate cow positions to minimize the largest cow count in any of the four regions.

Level: Medium5 of 10
Topics: Sorting, Prefix sum, Brute force
Solved: No attempts yet

Problem

Farmer John's $N$ cows stand at distinct points $(x_1, y_1), \ldots, (x_N, y_N)$ on his two-dimensional farm ( $1 \le N \le 100{,}000$ , and every $x_i$ and $y_i$ is a positive odd integer of size at most $1{,}000{,}000$ ). FJ wants to divide the field by building a north-south fence with equation $x = a$ . The fence is effectively infinite in length, and $a$ is an even integer, so the fence never passes through the position of a cow. He also builds an east-west fence with equation $y = b$ , where $b$ is an even integer as well. The two fences cross at the point $(a, b)$ and together cut the field into four regions.

FJ wants to choose $a$ and $b$ so that the cows in the four regions are reasonably balanced, with no region holding too many cows. Let $M$ be the largest number of cows in one of the four regions. FJ wants to make $M$ as small as possible. Determine that smallest possible value of $M$ .

Input

The first line contains a single integer $N$ . Each of the next $N$ lines contains the $x$ and $y$ coordinates of one cow, separated by a space.

Output

Print the smallest value of $M$ that FJ can achieve by placing the two fences optimally.

Examples2

Example 1
Input
```
7
7 3
5 5
7 13
3 1
11 7
5 3
9 1
```
Expected output
```
2
```
Example 2
Input
```
4
1 1
1 3
3 1
3 3
```
Expected output
```
1
```