题目描述

在二维平面上有 $N$ 个编号为 $1$ 到 $N$ 的房屋，第 $i$ 个房屋的坐标为 $(x_i, y_i)$。

我们使用切比雪夫距离来计算两个房屋之间的距离。即，房屋 $i$ 和 $j$ 之间的距离为 $\\max(|x_i - x_j|, |y_i-y_j|)$。

有 $\\frac{N(N-1)}{2}$ 对由两个不同房屋组成。对于这些对中的每一对，我们将计算两个房屋之间的距离，然后我们将按照降序排序这些距离，以得到一个长度为 $\\frac{N(N-1)}{2}$ 的序列。找出这个序列从开头开始的第二个值。

约束条件

• 输入中的所有值都是整数。
• $3 \le N \le 2 \times 10^{5}$
• $-10^{9} \le x_i, y_i \le 10^{9}$

输入

从标准输入读入数据，格式如下：

$N$ $x_{1}$ $y_{1}$ $\vdots$ $x_{N}$ $y_{N}$

输出

打印出不同房屋之间的距离按降序排序的序列中从开头开始的第二个值。

示例输入 1

3
0 0
1 2
4 0

示例输出 1

3

• 房屋 $1$ 和 $2$ 之间的距离为 $2$。
• 房屋 $1$ 和 $3$ 之间的距离为 $4$。
• 房屋 $2$ 和 $3$ 之间的距离为 $3$。
• 将这些按降序排序，得到 $(4, 3, 2)$，从开头开始的第二个值是 $3$。

示例输入 2

4
0 0
0 0
1 0
0 1

示例输出 2

1

• 可能存在多个坐标相同的房屋。

示例输入 3

20
407 361
167 433
756 388
-551 -47
306 -471
36 928
338 -355
911 852
288 70
-961 -769
-668 -386
-690 -378
182 -609
-677 401
-458 -112
184 -131
-243 888
-163 471
-11 997
119 544

示例输出 3

1766