Balanced Cow Partition

Farmer John has N cows located at distinct positions on an infinite 2D plane. The i^th cow is at position \( (x_i, y_i) \), where \( 1 \leq N \leq 10^5 \) and each coordinate \( x_i, y_i \) is a positive odd integer not exceeding \( 10^6 \).

FJ wants to construct two fences: a vertical fence given by the line \( x=a \) and a horizontal fence given by the line \( y=b \). In order to avoid cutting through any cow, both \( a \) and \( b \) must be even numbers. The intersection of these two fences at \( (a,b) \) divides the farm into four regions.

Let \( M \) be the maximum number of cows in any one of these four regions. Your task is to choose \( a \) and \( b \) such that \( M \) is minimized.

Note: Since all cow coordinates are odd, choosing \( a=x_i+1 \) and \( b=y_i+1 \) for some cow guarantees the fence will not pass through any cow.

inputFormat

The first line contains a single integer \( N \), the number of cows.

Each of the next \( N \) lines contains two space-separated integers \( x_i \) and \( y_i \), indicating the coordinates of a cow.

It is guaranteed that \( x_i \) and \( y_i \) are positive odd integers not exceeding \( 10^6 \), and no two cows occupy the same position.

outputFormat

Print the minimum possible value of \( M \), the maximum number of cows found in any of the four regions after placing the fences optimally.

sample

3
1 1
3 3
5 5

2