题目描述

在二维平面上，有 $n$ 个点，坐标分别记为 $(x_i,y_i)$。请找出一条平行于X轴与一条平行于Y轴的直线，将二维平面分成四部分，且在这四块区域里，点的分布尽量均匀——记 $a$，$b$，$c$，$d$ 为四块区域中点的数量，请找到一个划分方案，使 $a$，$b$，$c$，$d$ 中的最大值最小。

为了避免某点坐标恰好穿过划分直线的情况，保证所有点的坐标都是奇数，并且规定划分直线的坐标只能选择偶数。

输入格式

第一行：一个整数 $n$。 第二行到第 $n+1$ 行：第 $i+1$ 行有两个奇数 $x_i$ 和 $y_i$。

输出格式

单个整数：表示所有方案中，$a$，$b$，$c$，$d$ 最大值的最小值。

4
1 1
1 5
5 5 
5 1

1

数据范围

• $1\leq x_i,y_i<200,000$
• 保证有 $x_1\leq x_2 \leq x_3...\leq x_n$。
• 对于 $30\%$ 数据，$1 \leq n \leq 100$；
• 对于 $60\%$ 数据，$1 \leq n \leq 5000$；
• 对于 $100\%$ 数据，$1\leq n\leq 100,000$。