[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$ 的最小值。

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

2