시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 25 14 14 56.000%

문제

Mr. JOI has a huge desk in his collection room, and there are a number of rare coins on it. To clean up the desk, he is going to rearrange the coins.

The desk can be regarded as a 2 000 000 001 × 2 000 000 001 grid. The columns are numbered from −1 000 000 000 through 1 000 000 000 from left to right, and the rows are numbered from −1 000 000 000 through 1 000 000 000 from bottom to top. The cell with the column number x and the row number y is denoted by (x, y).

There are 2N coins. Currently, the i-th coin (1 ≤ i ≤ 2N) is placed at the cell (Xi, Yi). Mr. JOI’s goal is to place a coin on each cell (x, y) with 1 ≤ x ≤ N and 1 ≤ y ≤ 2. In order not to hurt the coins, the only operation he can perform is to choose a coin and move it to one of the neighboring cells (a cell neighbors another if and only if they share an edge). It is allowed that multiple coins are placed on a cell at some point. He wants to achieve the goal with as few operations as possible.

Write a program which, given the number of coins and the cells where the coins are currently placed, calculates the minimum number of operations needed to achieve the goal.

입력

Read the following data from the standard input.

N
X1 Y1
.
.
.
X2N Y2N

출력

Write one line to the standard output. The output should contain the minimum number of operations needed to achieve the goal.

제한

  • 1 ≤ N ≤ 100 000.
  • −1 000 000 000 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ 2N).
  • −1 000 000 000 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ 2N).

예제 입력 1

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

예제 출력 1

15

In this sample input, 6 coins are placed as the figure below. The goal is to collect the coins inside the thick lines.

For example, Mr. JOI can achieve the goal with 15 operations by the following moves:

  • The 1st coin: (0, 0) → (1, 0) → (1, 1) → (1, 2)
  • The 2nd coin: (0, 4) → (1, 4) → (1, 3) → (2, 3) → (3, 3) → (3, 2)
  • The 3rd coin: (4, 0) → (4, 1) → (3, 1)
  • The 5th coin: (2, 5) → (2, 4) → (2, 3) → (2, 2)
  • The 6th coin: (−1, 1) → (0, 1) → (1, 1)

As he cannot achieve the goal with 14 or less operations, you should output 15

예제 입력 2

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

예제 출력 2

9

Multiple coins may be placed on a cell.

예제 입력 3

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

예제 출력 3

8000000029