有 $N$ 个城市位于平面上的不同位置。这些城市用从 $1$ 到 $N$ 的整数编号表示。城市 $i$ 与城市 $i+1$ 之间存在一条道路，记为 $R_i$（$i=1,\dots,N-1$）。因此一共存在 $N-1$ 条道路。 对于每个 $i=1,\dots,N-1$，若城市 $i$ 的坐标为 $(x_i,y_i)$，则道路 $R_i$ 的长度定义为 $|x_i-x_{i+1}|+|y_i-y_{i+1}|$。

城市 $i$ 与城市 $j$ 之间的一条路径 $P$，是从 $i$ 移动到 $j$ 时经过的道路的集合。路径 $P$ 的长度是 $P$ 中所有道路长度之和。我们关心城市集合的直径。直径定义为所有城市对之间最短路径长度的最大值。当然，在上述给定的城市结构中，城市的直径等于城市 $1$ 与城市 $N$ 之间路径的长度。

我们计划在这些城市中选取一对城市，新建一条道路。将这条新道路记为 $R_{\text{new}}$。若 $R_{\text{new}}$ 连接城市 $a$ 与城市 $b$，则其长度定义为 $|x_a-x_b|+|y_a-y_b|$。 问题是，如何选择新建的道路 $R_{\text{new}}$，使得城市集合的直径最小。

给定 $N$ 个城市的位置，请编写程序，确定新建道路 $R_{\text{new}}$，使得城市的直径最小，并输出该直径的最小值。

例如，在下图中给出了 $4$ 个城市以及连接城市的 $3$ 条道路（实线）。可以新建的道路候选有 $3$ 条（城市 $1$ 与 $4$，$1$ 与 $3$，$4$ 与 $2$）。其中如图所示在城市 $4$ 与城市 $2$ 之间新建道路（虚线），城市的直径为 $6$，且这是最小值。

你需要为评测系统实现下面这一函数，并使用该函数提交答案。

• long long shortcut(int N, long long X[], long long Y[]); 该函数以城市数量 $N$，以及表示各城市位置的数组 X[0..N-1] 和 Y[0..N-1] 作为参数。其中 X[] 和 Y[] 是长度为 $N$ 的向量，X[i] 与 Y[i] 分别表示城市 $i+1$ 的 $x$ 坐标和 $y$ 坐标。 函数的返回值是在新建道路加入后，城市直径的最小可能值。

实现细节

你必须提交且仅提交一个名为 shortcut.cpp 的文件。该文件中需要实现如下函数：

• long long shortcut(int N, long long X[], long long Y[]);

该函数的行为应与上述描述一致。当然，你可以在内部定义并使用其他函数。提交的代码不得进行输入输出操作，也不得访问其他文件。

评测程序示例

给定的评测程序将按如下格式读取输入：

• 第 1 行：$N$（城市的数量，$3 \le N \le 250{,}000$）
• 第 2 行到第 $N+1$ 行：第 $i$ 行给出城市 $i-1$ 的坐标 $(x,y)$，其中 $-10^9 \le x,y \le 10^9$

评测程序将输出在新建道路加入后，城市直径的最小值。

子任务

• 子任务 1（4 分）：$N \le 40$
• 子任务 2（6 分）：$N \le 100$
• 子任务 3（12 分）：$N \le 300$
• 子任务 4（25 分）：$N \le 2{,}000$
• 子任务 5（40 分）：$N \le 50{,}000$
• 子任务 6（13 分）：无额外限制

样例数据

输入样例 1

4
1 2
2 2
2 1
1 1

输出样例 1

2

输入样例 2

4
1 2
3 3
4 1
2 3

输出样例 2

6