题目描述

题目译自 Ukrainian Olympiads in Informatics 2025 Stage 4 Day2 T1. Проста підпослідовність

对于笛卡尔平面上的一对点 $(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

在第二个样例中，最优配对为 $[(18, 0), (14, 0)]$、$[(3, 0), (1, 0)]$ 和 $[(8, 0), (10, 0)]$，这是唯一的最优配对。每对点之间的曼哈顿距离分别为 $4$、$2$ 和 $2$。

4
3 0
0 1
5 0
2 1
6 0
3 0
5 1
2 1

2

在第三个样例中，最优配对为 $[(0, 1), (2, 1)]$、$[(2, 1), (3, 0)]$、$[(3, 0), (5, 0)]$ 和 $[(5, 1), (6, 0)]$。每对点之间的曼哈顿距离均为 $2$。

数据范围与提示

详细子任务附加限制及分值如下表所示：