Metro City 的两家自行车快递公司多年来一直处于竞争状态，互相争夺客户。最近，他们意识到如果能吸引新客户，情况会更好。问题在于，随着时间的推移，每家公司的客户在城市中分布得过于分散，导致部分配送时间长得令人无法接受，从而引发了客户不满并损害了声誉。

这两家公司希望划分现有的客户群，以便每家公司都能打出“我们保证配送时间不超过 M 分钟”的广告，从而吸引新客户。Metro City 的街道呈网格状布局，建筑物位于网格的整数坐标处。快递员必须沿着这些道路行驶——他们不能穿过建筑物。在 $x$ 或 $y$ 方向上移动一个单位距离需要一分钟。

请划分当前的客户群，以最小化两家公司中任意一家公司所需的“最长配送时间”。其中，某家公司的最长配送时间定义为该公司快递员从该公司的任意一个客户处前往该公司其他任意一个客户所需的最长时间。

• 当快递员到达客户的 $(x, y)$ 地址时，配送即视为完成。在客户建筑物内寻找的时间不计入配送时间。
• 快递员从一个客户前往另一个客户时，可以经过属于同一家公司或另一家公司的客户，这是允许的。经过客户时不会产生额外的延误。
• 如果某家公司最终只有一个客户，该公司会安排人员在现场为该建筑物内的客户提供服务。这种情况下的配送时间视为零。

输入格式

输入的第一行包含一个整数 $N$，表示需要划分的客户数量。$2 < N \le 1000$。 接下来 $N$ 行，每行包含一对整数 $x$ 和 $y$，表示一个客户的位置。$0 \le x, y \le 1000$。

输出格式

输出一行，包含两家公司所需的最长配送时间中的最小值（即两家公司各自的最长配送时间中的最大值）。

样例

输入 1

6
1 1
4 1
1 5
10 10
10 8
7 10

输出 1

7

输入 2

7
0 0
100 100
0 100
100 0
50 50
0 50
100 50

输出 2

100