Problem Background

JOI 2019 Final T4

Due to the large number of data points, only a portion of the data will be evaluated for this problem.

Problem Description

JOI's collection room features a massive table adorned with many rare coins. To tidy up the table, he needs to rearrange the coins.

The table can be considered as a grid of size $(2 \times 10^9 + 1) \times (2 \times 10^9 + 1)$. JOI has $2N$ coins. Initially, the $i$-th coin $(1 \le i \le 2N)$ is placed at coordinates $(X_i, Y_i)$. JOI's goal is to have exactly one coin in each grid cell $(x, y)$ where $1 \le x \le N$ and $1 \le y \le 2$. The only operation he can perform is to select a coin and move it to an adjacent grid cell (two cells are adjacent if and only if they share a common edge). During the movement of coins, it is allowed for two coins to occupy the same cell. JOI aims to achieve his goal with the minimum number of operations.

Given the number of coins and their initial positions, write a program to calculate the minimum number of operations required to achieve JOI's goal.

Input Format

The first line contains an integer $N$.

The next $2N$ lines each contain two integers $X_i$ and $Y_i$.

Output Format

Output a single integer, which is the minimum number of operations required to achieve the goal.

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

Explanation for Sample #1:

One valid sequence of moves is:

• First coin: $(0,0) \rightarrow (1,0) \rightarrow (1,1) \rightarrow (1,2)$
• Second coin: $(0,4) \rightarrow (1,4) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,2)$
• Third coin: $(4,0) \rightarrow (4,1) \rightarrow (3,1)$
• Fourth coin: remains stationary
• Fifth coin: $(2,5) \rightarrow (2,4) \rightarrow (2,3) \rightarrow (2,2)$
• Sixth coin: $(-1,1) \rightarrow (0,1) \rightarrow (1,1)$

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

For $8\%$ of the data, $N \le 10$.

For $37\%$ of the data, $N \le 1000$.

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

见题面 Input 部分

见题面 Output 部分