Problem Description

JOI's collection room has a very large table, on which there are many valuable coins. To clean the table, JOI decided to arrange the coins.

The table is divided into a grid of $2,000,000,001 \times 2,000,000,001$ squares. Columns are numbered from left to right starting from $-1,000,000,000$ to $1,000,000,000$, and rows are numbered from bottom to top starting from $-1,000,000,000$ to $1,000,000,000$. A square with column number $x$ and row number $y$ is represented as $(x, y)$.

There are $2N$ coins. Currently, the $i$-th ($1 \leq i \leq 2N$) coin is placed on the square $(X_i, Y_i)$. JOI's goal is to have one coin on each of the $2N$ squares represented by $(x, y)$ where $1 \leq x \leq N$ and $1 \leq y \leq 2$. To avoid damaging the coins, only the operation "select one coin and move it to one of the squares adjacent by edge to the square it is currently on" is allowed. Multiple coins can be on the same square during the process. JOI wants to achieve the goal with the minimum number of operations.

Given the number of coins and the squares where the coins are currently placed, write a program to find the minimum number of operations needed to achieve the goal.

Input Format

The input is given from the standard input in the following format:

$N$ $X_1$ $Y_1$ $\vdots$ $X_{2N}$ $Y_{2N}$

Output Format

Output the minimum number of operations needed to achieve the goal on the standard output in one line.

Sample Input and Output

Sample Input #1

3
0 0
0 4
4 0
2 1
2 5
-1 1

Sample Output #1

15

Sample Input #2

4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1

Sample Output #2

9

Sample Input #3

5
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000
-1 -5
-2 2
2 8
4 7
-2 5
7 3

Sample Output #3

8000000029

Notes/Hints

Constraints

• $1 \leq N \leq 100,000$.
• $-1,000,000,000 \leq X_i \leq 1,000,000,000$ ($1 \leq i \leq 2N$).
• $-1,000,000,000 \leq Y_i \leq 1,000,000,000$ ($1 \leq i \leq 2N$).

Subtasks

1. ($8$ points) $N \leq 10$.
2. ($29$ points) $N \leq 1,000$.
3. ($63$ points) No additional constraints.

Sample Explanation 1

In this input example, 6 coins are placed as shown in the figure below. The goal is to gather the coins in the positions indicated by the thick frame.

For example, moving the coins as follows achieves the goal in 15 operations:
- 1st coin: $(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (1, 2)$
- 2nd coin: $(0, 4) \rightarrow (1, 4) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 2)$
- 3rd coin: $(4, 0) \rightarrow (4, 1) \rightarrow (3, 1)$
- 5th coin: $(2, 5) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (2, 2)$
- 6th coin: $(-1, 1) \rightarrow (0, 1) \rightarrow (1, 1)$

It is not possible to achieve the goal in 14 or fewer operations, so output 15.

Sample Explanation 2

Multiple coins may be placed on the same square.

见题面 Input 部分

见题面 Output 部分