题目描述

Catarina loves all cats that live in her neighborhood. Her lifelong dream is to design a large cat-seeing circuit, so that every day she can go out and greet the cats while doing some exercise. Catarina's neighborhood can be represented as the 2D plane, with the North-South direction aligned with the $y$-axis. A cat-seeing circuit that visits $m$ cats consists of exactly $m$ steps. Catarina chooses a starting position $(x_0, y_0)$ and faces one of the four cardinal directions. For each step $i = 1, 2, \ldots, m$ the following occurs:

• Catarina chooses a value $k_i > 0$ and walks $k_i$ units from $(x_{i-1}, y_{i-1})$ straight ahead in her current direction, stopping at the location of a cat that she has not greeted during any previous step.
• Catarina greets the cat, taking some time to appreciate its beauty.
• Without turning around, Catarina walks another $k_i$ units straight ahead in her current direction, stopping at a position $(x_i, y_i)$.
• Catarina turns $90^\circ$ either clockwise or counterclockwise, facing again one of the four cardinal directions.

After completing all $m$ steps, Catarina must be back to her starting position $(x_0, y_0)$, facing her initial direction. Notice that the length of the cat-seeing circuit is $\sum_{i=1}^m 2k_i$. When $m = 0$, the cat-seeing circuit has length $0$.

Catarina knows the location of the $N$ cats that live in her neighborhood. Surprisingly, no two cats have the same $x$-coordinate or the same $y$-coordinate. Your task is to determine the maximum length that a cat-seeing circuit can have.

输入格式

The first line contains an integer $N$ ($1 \le N \le 4000$) indicating the number of cats.

Each of the next $N$ lines describes a cat with two integers $X$ and $Y$ ($-10^8 \le X, Y \le 10^8$), representing that the cat has coordinates $(X, Y)$.

No two cats have the same $x$-coordinate or $y$-coordinate (they differ in both of them).

输出格式

Output a single line with an integer indicating the maximum length that a cat-seeing circuit can have.

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

提示

Explanation of Sample 1:

In this case there is a circuit of length $16$ that visits all the cats, but it is not a cat-seeing circuit because the cat at coordinates $(0, 0)$ is greeted twice.

Explanation of Sample 2:

The picture below shows the location of the cats with small circles, together with a maximum-length cat-seeing circuit that visits all of them. The length of the circuit is $32$.

:::align{center} :::

Explanation of Sample 3:

It is possible to visit $m = 6$ of the $N = 7$ cats with a cat-seeing circuit of length $24$.

:::align{center} :::