对于笛卡尔平面上的一对点 $(x_1, y_1)$ 和 $(x_2, y_2)$，我们定义它们之间的 曼哈顿距离 为 $|x_1-x_2|+|y_1-y_2|$。例如，对于点对 $(4, 1)$ 和 $(2, 7)$，它们之间的 曼哈顿距离 为 $|4-2|+|1-7| = 2+6 = 8$。
你将得到平面上 $2 \cdot n$ 个点，它们的坐标是整数。所有给出的点的 $y$ 坐标要么是 $0$，要么是 $1$。
请将这些点划分成 $n$ 对，使得每个点恰好属于一对，并且使得每对点之间的最大 曼哈顿距离 尽可能小。
输入
第一行包含一个整数 $n$ $(1 \le n \le 10^5)$。
接下来的 $2 \cdot n$ 行中，每行包含两个整数 $x_i$ 和 $y_i$ $(0 \le x_i \le 10^9, 0 \le y_i \le 1)$~--- 表示该点的坐标。
输出
输出一个整数~--- 最优划分中每对点之间的最大 曼哈顿距离。
示例
输入
1 3 1 1 0
输出
3
输入
3 18 0 3 0 1 0 10 0 8 0 14 0
输出
4
输入
4 3 0 0 1 5 0 2 1 6 0 3 0 5 1 2 1
输出
2
说明
在第二个样例中，划分为 $[(18, 0), (14, 0)]$, $[(3, 0), (1, 0)]$, 和 $[(8, 0), (10, 0)]$ 是唯一的最优划分。在这个划分中，每对点之间的 曼哈顿距离 分别为 $4$, $2$, 和 $2$。
在第三个样例中，划分为 $[(0, 1), (2, 1)]$, $[(2, 1), (3, 0)]$, $[(3, 0), (5, 0)]$, 和 $[(5, 1), (6, 0)]$ 是一个最优划分。这个划分中每对点之间的 曼哈顿距离 都为 $2$。
第三个样例的图示
评分
- （$2$ 分）：$n = 1$；
- （$3$ 分）：$x_i = 0$ 对于 $1 \le i \le 2\cdot n$；
- （$4$ 分）：$n \le 4$；
- （$11$ 分）：$n \le 10$；
- （$14$ 分）：$y_i = 0$ 对于 $1 \le i \le 2\cdot n$；
- （$10$ 分）：$x_i \neq x_j$ 对于 $1 \le i < j \le 2\cdot n$；
- （$29$ 分）：$n \le 1000$；
- （$27$ 分）：没有额外限制。