P16557 [ICPC 2026 LAC] Kitten Greetings

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.

**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}  :::