题目描述

[ARC121A] 2nd Greatest Distance

在二维平面上有 $N$ 个使用编号 $1$ 到 $N$ 的数字标记的房子。 房子 $i$ 位于 $(x_i,y_i)$。

房子 $i,j$ 之间的距离是 $\max(\left|{x\_i-x\_j}\right|, \left|{y\_i-y\_j}\right|)$。

有总共 $N(N-1)/2$ 对不同的房子，对于每一对不同的房子，计算它们之间的距离，把距离值按降序排列成一个长度为 $N(N-1)/2$ 的数列。请输出这个数列的第二个数字。

输入格式

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

输出格式

对于每一个样例，输出第二大的数字。

样例 1

输入

3
0 0
1 2
4 0

输出

3

样例 2

输入

4
0 0
0 0
1 0
0 1

输出

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

输出

1766

说明/提示

样例输入 #1

3
0 0
1 2
4 0

样例输出 #1

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

• 所有的输入都保证为整数
• $3 \leqslant N \leqslant 2 \times 10^5$
• $-10^9 \leqslant x_i, y_i \leqslant 10^9$