K. Kitten Greetings
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \gt 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.

Input

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

Each of the next $$$N$$$ lines describes a cat with two integers $$$X$$$ and $$$Y$$$ ($$$-10^{8} \leq X, Y \leq 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

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

Examples
Input
5
1 2
2 1
0 0
-1 -2
-2 -1
Output
0
Input
6
4 0
0 4
2 -1
-1 2
-4 3
3 -4
Output
32
Input
7
2 1
0 -1
5 5
3 0
4 4
6 2
1 -2
Output
24
Note

Explanation for example 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 for example 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$$$.

Explanation for example 3

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