Problem
Farmer John's cows are at different points (x1,y1)…(xn,yn ) its fields (1≤N≤100,000, all xi and yi are positive odd integers not exceeding 1,000,000. The FD wants to divide his field with a fence of infinite length from the north to the south, described by the equation x=a (a is an even integer, so it is ensured that the fence does not pass through the position of any cow.) He also wants to build a fence of infinite length from east to west, which is described by the equation y=b, where b is an even integer These two fences intersect at (a,b), and together divide the field into four regions.
The FD wants to choose a and b in such a way that they get a "balanced" number of cows in all regions, i.e. so that there is no region that contains too many cows. Let M be the maximum number of cows in these four regions, the FD wants M to be as small as possible. Help FD determine this minimum possible value for M.
INPUT FORMAT:
The first line of input contains one integer, N. Each of the next n lines contains the location of one cow, indicated by its x and y coordinates.
OUTPUT FORMAT:
Print the minimum possible value of M that can reach the PD with the optimal arrangement of fences.
|
Enter |
Output |
|
7
73
5 5
7 13
3 1
117
5 3
9 1
|
2 |