你是“加州大学洛杉矶分校作弊与诡秘学生帮”（简称“CS 学生”）的一员。你的目标？在每场考试中，以最高效的方式进行作弊。你们帮派的老大不知为何总能在考试前五分钟拿到所有问题的答案（虽然不清楚老大是怎么做到的，但成员们怀疑有内部助教的协助）。因此，帮派需要一种在考试期间分享答案的方法！

帮派的作弊策略很简单。帮派中的一名成员从座位上站起来，悄悄走到另一名成员身边，分享他们知道的所有答案。一旦某个学生得知了答案，他们就会永远记住，并可以分享给下一个学生。平面上有 $N$ 个学生，表示为点，你可以假设任意两个学生 $(x_i, y_i)$ 和 $(x_j, y_j)$ 之间的最短距离为他们的曼哈顿距离 $|x_i - x_j| + |y_i - y_j|$。每个学生移动 $d$ 的距离需要花费 $d$ 秒。在与其他学生分享答案后，该学生随后返回自己的座位（学生在返回座位前只能通知一名学生）。

为了避开教授的视线，在学生站起来之前，帮派中的任意成员会提出一个问题，教授会转过身并在白板上进行解答，因此你不需要担心学生被抓。但你必须小心！同一时间只能有一名学生站起来，并且必须直接返回座位，否则教授就会发现，而你们将不幸地被称为“加州大学洛杉矶分校极度愚蠢学生帮”。

教授在考试前已经确定了座位布局并与全班分享。给定这个座位布局，即平面上的 $N$ 个点 $(x_i, y_i)$ 的列表，你能否帮助帮派中的每个人尽快获得所有答案，以确保每个人都能按时完成考试？

输入格式

第一行包含一个整数 $N$，表示参加考试的帮派学生人数。

接下来的 $N$ 行，每行包含两个空格分隔的整数 $x_i$ 和 $y_i$，表示第 $i$ 个学生在考场中的位置。($1 \le N \le 2\,000$, $-1\,000 \le x_i, y_i \le 1\,000$)

输出格式

输出单行，包含一个整数，表示确保每个人都获得考试所有答案所需的最少时间（以秒为单位）。

样例

输入样例 1

5
0 0
0 1
1 1
-1 0
0 -1

输出样例 1

8

输入样例 2

5
0 0
4 2
6 1
7 7
7 0

输出样例 2

36