Load Balancing

Interview

Time limit1sMemory limit512 MB

Summary

John places one vertical and one horizontal fence to minimize the largest cow count in the four regions.

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

Problem

Farmer John's $N$ cows stand at distinct positions $(x_1, y_1), \ldots, (x_N, y_N)$ on his two dimensional farm ( $1 \le N \le 1000$ ). Every $x_i$ and $y_i$ is a positive odd integer of size at most $1{,}000{,}000$ .

To split the farm, John builds a very long fence running north to south along the line $x = a$ . The value $a$ is an even integer, so the fence never passes through the position of a cow. He also builds a very long fence running east to west along the line $y = b$ , where $b$ is an even integer as well. The two fences meet at the point $(a, b)$ and cut the farm into four regions.

Let $M$ be the number of cows in the region that holds the most cows. John wants to pick $a$ and $b$ so that $M$ is as small as possible. Find the smallest value of $M$ .

Input

The first line contains the number of cows $N$ . Each of the next $N$ lines contains two integers $x$ and $y$ separated by a space, the position of one cow.

Output

Print on one line the smallest value of $M$ that John can reach by placing the two fences optimally.

Examples3

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