You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

本题与 白金组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

Farmer John 的 $N$ 头奶牛（$1 \leq N \leq 1000$）散布在整个农场上。整个农场是一个无限大的二维平面，第 $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