Description

In Mr. JOI’s collection room, there is a huge table with many rare coins on it. To tidy up the table, he wants to rearrange the coins.

The tabletop can be viewed as a grid of size $(2\times 10^9+1)\times (2\times 10^9+1)$. Mr. JOI has $2N$ coins. Initially, the $i$-th coin $(1\le i\le 2N)$ is placed on the cell with coordinates $(X_i,Y_i)$. Mr. JOI’s goal is to place exactly one coin on every cell $(x,y)$ such that $1\le x \le N,1\le y\le 2$. To avoid damaging the coins, the only operation he can do is to choose one coin and move it to an adjacent cell (we say two cells are adjacent if and only if they share a common edge). During the moving process, it is allowed for two coins to be in the same cell. Mr. JOI wants to achieve the goal using as few operations as possible.

Given the number of coins and their initial positions, write a program to compute the minimum number of operations needed to achieve Mr. JOI’s goal.

Input Format

The first line contains an integer $N$.

The next $2N$ lines follow. The $i$-th of these lines contains two integers $X_i$ and $Y_i$.

Output Format

Output one integer in one line, representing the minimum number of operations needed to achieve the goal.

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

15

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

9

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

8000000029

Hint

Sample Explanation

Sample explanation 1:

One valid moving plan is:

Coin 1: $(0,0)\rightarrow(1,0)\rightarrow(1,1)\rightarrow(1,2)$

Coin 2: $(0,4)\rightarrow(1,4)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(3,2)$

Coin 3: $(4,0)\rightarrow(4,1)\rightarrow(3,1)$

Coin 4: does not move

Coin 5: $(2,5)\rightarrow(2,4)\rightarrow(2,3)\rightarrow(2,2)$

Coin 6: $(-1,1)\rightarrow(0,1)\rightarrow(1,1)$

It can be proven that Mr. JOI cannot achieve the goal with fewer than $15$ moves.

Constraints

Subtask 1 (8 points): $N\le 10$.

Subtask 2 (29 points): $N\le 1000$.

Subtask 3 (63 points): no additional constraints.

For $100\%$ of the testdata, $N\le 10^5,-10^9\le X_i,Y_i\le 10^9$.

Translated by ChatGPT 5