[USACO16FEB] Load Balancing P

题目背景

*本题与 [银组同名题目](/problem/P3138) 在题意上一致,唯一的差别是数据范围。*

题目描述

Farmer John 的 $N$ 头奶牛($1 \leq N \leq 10^5$)散布在整个农场上。整个农场是一个无限大的二维平面,第 $i$ 头奶牛的坐标是 $(x_i,y_i)$(保证 $x_i,y_i$ 均为正奇数,且 $x_i,y_i \leq 10^6$),且没有任意两头奶牛在同一位置上。 FJ 希望修建一条竖直方向的栅栏,它的方程是 $x=a$,他还希望修建一条水平方向的栅栏,它的方程是 $y=b$。为了防止栅栏经过奶牛,$a,b$ 均要求是偶数。容易发现,这两个栅栏会在 $(a,b)$ 处相交,将整个农场分割为四个区域。 FJ 希望这四个区域内的奶牛数量较为均衡,尽量避免一个区域奶牛多而另一个区域奶牛少的情况。令 $M$ 为四个区域里奶牛最多区域的奶牛数量,请帮 FJ 求出 $M$ 的最小值。

输入输出格式

输入格式


第一行一个整数 $N$。 接下来 $N$ 行,每行两个整数 $x_i,y_i$,描述第 $i$ 头奶牛的位置。

输出格式


输出 $M$ 的最小值。

输入输出样例

输入样例 #1

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

输出样例 #1

2