题目描述

Catarina 喜爱她社区中的所有猫。她的毕生梦想是设计一条大型的观猫路线，这样她每天都可以出门散步，同时向猫咪们打招呼。Catarina 的社区可以表示为二维平面，南北方向与 $y$ 轴对齐。一条拜访了 $m$ 只猫的观猫路线恰好包含 $m$ 步。Catarina 选择一个起始位置 $(x_0, y_0)$，并面向四个基本方向之一。对于每一步 $i = 1, 2, \ldots, m$，发生以下事件：

• Catarina 选择一个正数 $k_i > 0$，从 $(x_{i-1}, y_{i-1})$ 沿当前方向直走 $k_i$ 个单位，停在一只猫所在的位置，且该猫在之前的任何步骤中都未被问候过。
• Catarina 向这只猫打招呼，花一些时间欣赏它的美丽。
• 在不转向的情况下，Catarina 再沿当前方向直走 $k_i$ 个单位，停在位置 $(x_i, y_i)$。
• Catarina 顺时针或逆时针旋转 $90^\circ$，再次面向四个基本方向之一。

完成所有 $m$ 步后，Catarina 必须回到她的起始位置 $(x_0, y_0)$，并且面向初始方向。注意观猫路线的总长度为 $\sum_{i=1}^m 2k_i$。当 $m = 0$ 时，观猫路线的长度为 $0$。

Catarina 知道她社区中 $N$ 只猫的位置。令人惊讶的是，没有两只猫具有相同的 $x$ 坐标或相同的 $y$ 坐标。你的任务是确定一条观猫路线可能达到的最大长度。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 4000$），表示猫的数量。

接下来 $N$ 行，每行描述一只猫，包含两个整数 $X$ 和 $Y$（$-10^8 \le X, Y \le 10^8$），表示该猫的坐标为 $(X, Y)$。

没有两只猫具有相同的 $x$ 坐标或相同的 $y$ 坐标（它们在两个坐标上都不同）。

输出格式

输出一行一个整数，表示一条观猫路线可能达到的最大长度。

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

0

6
4 0
0 4
2 -1
-1 2
-4 3
3 -4

32

7
2 1
0 -1
5 5
3 0
4 4
6 2
1 -2

24

提示

样例 1 解释：

在此情况下，存在一条长度为 $16$ 且拜访了所有猫的回路，但它不是观猫路线，因为坐标为 $(0, 0)$ 的猫被问候了两次。

样例 2 解释：

下图用小圆圈显示了猫的位置，以及一条拜访了所有猫且长度最大的观猫路线。该路线的长度为 $32$。

:::align{center} :::

样例 3 解释：

可以用一条长度为 $24$ 的观猫路线拜访 $N = 7$ 只猫中的 $m = 6$ 只。

:::align{center} :::

翻译由 DeepSeek V4 Pro 完成