Coin Collecting

시간 제한1초메모리 제한512 MB

요약

거대한 격자 위의 동전 2N개를 1 이상 N 이하의 x와 1 이상 2 이하의 y마다 한 개씩 놓이도록 옮길 때 필요한 최소 이동 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

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).

예제3

예제 1
입력
```
3
0 0
0 4
4 0
2 1
2 5
-1 1
```
예상 출력
```
15
```
예제 2
입력
```
4
2 1
2 1
2 1
3 1
3 1
3 1
3 1
3 1
```
예상 출력
```
9
```

예제 3

입력

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

예상 출력

8000000029