1440: 平均分配2

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:50 通过:11

题目描述

农夫约翰的n只奶牛分别站在(x1,y1),(x2,y2)..(xn,yn)的二维平面上,每个xiyi都是正整数,并且都是奇数,所有xiyi都不超过B。约翰想要修建两个很长的栅栏,第一个栅栏是x=a这条线(垂直),第二个栅栏是y=b这条线(水平),ab都是偶数。这两个栅栏可以把所有的奶牛分在4个不同的区域内。

约翰想要选择最好的ab,使得4个区域的奶牛数量尽量平衡。如果4个区域中最多的一个区域有m头奶牛,那么所谓的平衡就是要使得这个m尽量小,现在请你帮助他来计算这个最小的m

输入格式

      输入文件第一行是一个正整数n,表示奶牛的数量,接下来n行,表示每个奶牛的坐标位置。

输出格式

       输出文件只有一行一个整数,表示最小的m

输入样例 复制

7
7 3
5 5
9 7
3 1
7 7
5 3
9 1

输出样例 复制

2

数据范围与提示

【数据说明】

1<=n<=10001<=B<=1000000