龙仁市（Yong-In）计划建设一个拥有 $N$ 个公交站的公交网络。每个公交站都位于街道拐角处。龙仁市是一座现代城市，因此其地图是一个由等大正方形街区组成的网格。

在这些公交站中，将选择两个作为枢纽 $H_1$ 和 $H_2$。这两个枢纽将通过一条直接的公交线路相互连接，其余 $N - 2$ 个公交站中的每一个都将直接连接到 $H_1$ 或 $H_2$ 中的一个（但不能同时连接到两个），且不连接到任何其他公交站。

任意两个公交站之间的距离是沿街道行驶的最短可能路径的长度。也就是说，如果一个公交站表示为 $(x, y)$，其中 $x$ 坐标为 $x$，$y$ 坐标为 $y$，那么两个公交站 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离为 $|x_1 - x_2| + |y_1 - y_2|$。如果公交站 $A$ 和 $B$ 连接到同一个枢纽 $H_1$，那么从 $A$ 到 $B$ 的路径长度是 $A$ 到 $H_1$ 的距离与 $H_1$ 到 $B$ 的距离之和。如果公交站 $A$ 和 $B$ 连接到不同的枢纽，例如 $A$ 连接到 $H_1$，$B$ 连接到 $H_2$，那么从 $A$ 到 $B$ 的路径长度是 $A$ 到 $H_1$ 的距离、$H_1$ 到 $H_2$ 的距离以及 $H_2$ 到 $B$ 的距离之和。

龙仁市的规划部门希望确保每位市民都能尽可能快地到达城市内的每个地方。因此，城市规划者希望选择两个公交站作为枢纽，并进行连接分配，使得在最终的公交网络中，任意两个公交站之间的最长路径长度尽可能短。

如果选择 $P$（包括两个枢纽的选择以及其他公交站到这两个枢纽的分配方案）中任意两点间的最长公交路径长度比选择 $Q$ 更短，则称选择 $P$ 优于选择 $Q$。你的任务是编写一个程序，计算出最优选择 $P$ 下的这一最长路径长度。

输入格式

你的程序需要从标准输入读取数据。

第一行包含一个正整数 $N$（$2 \le N \le 500$），表示公交站的数量。

接下来的 $N$ 行，每行包含一个公交站的 $x$ 坐标和 $y$ 坐标。$x$ 和 $y$ 坐标均为不超过 $5000$ 的正整数。没有两个公交站位于同一位置。

输出格式

你的程序需要写入标准输出。

输出包含一行，一个正整数，表示对于输入数据，任意两点间最长公交路径长度的最小值。

样例

输入 1

6
1 7
16 6
12 4
4 4
1 1
11 1

输出 1

20

输入 2

7
7 9
10 9
5 3
1 1
7 2
15 6
17 7

输出 2

25

说明

下图展示了上述输入对应的公交网络。

在样例 1 中，如果选择公交站 3 和 4 作为枢纽，则最长路径要么在公交站 2 和 5 之间，要么在公交站 2 和 1 之间。没有更优的枢纽选择方案，因此答案为 20。

对于样例 2 中的公交网络，如果选择公交站 5 和 6 作为枢纽，则最长路径在公交站 2 和 7 之间。没有更优的枢纽选择方案，因此答案为 25。

样例 1 的公交网络

样例 2 的公交网络

子任务

如果你的程序在时间限制内输出测试用例的正确答案，你将获得该测试用例的满分，否则该测试用例得 0 分。