Load Balancing (Silver)
Farmer John's n cows are each standing at distinct locations (x[1], y[1]) ... (x[n], y[n]) on his two-dimensional farm. FJ wants to partition his field by building a long (effectively infinite-length) north-south fence with equation x = a (a will be an even integer, thus ensuring that he does not build the fence through the position of any cow). He also wants to build a long (effectively infinite-length) east-west fence with equation y = b, where b is an even integer. These two fences cross at the point (a, b) and together they partition his field into four regions.
FJ wants to choose a and b so that the cows appearing in the four resulting regions are reasonably "balanced", with no region containing too many cows. Letting m be the maximum number of cows appearing in one of the four regions, FJ wants to make m as small as possible. Please help him determine this smallest possible value for m.
Input
The first line contains a single integer n (1 ≤ n ≤ 1000). The next n lines each contain the location of a single cow, specifying its x and y coordinates (positive odd integers of size at most 10^6).
Output
Print the smallest possible value of m that FJ can achieve by positioning his fences optimally.