E - Traveler Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

数直線上にボール 1 からボール N までの N 個のボールがあります。
ボール i は座標 X_i にあります。
各ボールには 1 以上 N 以下の整数で表される色がついていて、ボール i の色は整数 C_i で表されます。
今座標 0 にいるあなたは、毎秒 1 の速さで数直線上を動き、全てのボールを回収してから再び座標 0 に戻ります。
このとき、ボールの色を表す整数を回収順に並べた時に広義単調増加となっている必要があります。
ボールを回収するにはボールと同じ座標にいる必要がありますが、ボールを回収できる時に必ずしも回収する必要はありません。
座標 0 を出発してから、全てのボールを回収して再び座標 0 に戻るまでにかかる時間の最小値を求めてください。

制約

  • 1 \le N \le 2 \times 10^5
  • |X_i| \le 10^9
  • X_i \neq X_j (i \neq j)
  • X_i \neq 0
  • 1 \le C_i \le N
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 C_1
X_2 C_2
X_3 C_3
\hspace{15pt} \vdots
X_N C_N

出力

答え [秒] を出力せよ。

入力例 1

5
2 2
3 1
1 3
4 2
5 3

出力例 1

12

以下のように行動するのが最適です。

  • 3 秒かけて座標 3 に移動し、ボール 2 を回収する
  • 1 秒かけて座標 2 に移動し、ボール 1 を回収する
  • 2 秒かけて座標 4 に移動し、ボール 4 を回収する
  • 1 秒かけて座標 5 に移動し、ボール 5 を回収する
  • 4 秒かけて座標 1 に移動し、ボール 3 を回収する
  • 1 秒かけて座標 0 に戻る

ボールの色を表す整数を回収順に並べると 1, 2, 2, 3, 3 と広義単調増加になっています。

入力例 2

9
5 5
-4 4
4 3
6 3
-5 5
-3 2
2 2
3 3
1 4

出力例 2

38

Score : 500 points

Problem Statement

There are N balls, called Ball 1 through N, on a number line.
Ball i is at the coordinate X_i.
Each ball has a color represented by an integer ID between 1 and N (inclusive); the ID of the color of Ball i is C_i.
You are now at the coordinate 0. You will collect all the balls by moving along the line at the speed of 1 per second, and then return to the coordinate 0.
Here, you have to collect the balls in a non-descending order of their IDs.
When collecting a ball, you have to be at the coordinate of that ball, but it is not mandatory to collect it when you are there.
Find the minimum time needed to start at the coordinate 0, collect all the balls, and return to the coordinate 0.

Constraints

  • 1 \le N \le 2 \times 10^5
  • |X_i| \le 10^9
  • X_i \neq X_j (i \neq j)
  • X_i \neq 0
  • 1 \le C_i \le N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 C_1
X_2 C_2
X_3 C_3
\hspace{15pt} \vdots
X_N C_N

Output

Print the number of seconds needed.

Sample Input 1

5
2 2
3 1
1 3
4 2
5 3

Sample Output 1

12

The optimal strategy is:

  • spend 3 seconds to reach the coordinate 3 and collect Ball 2;
  • spend 1 second to reach the coordinate 2 and collect Ball 1;
  • spend 2 seconds to reach the coordinate 4 and collect Ball 4;
  • spend 1 second to reach the coordinate 5 and collect Ball 5;
  • spend 4 seconds to reach the coordinate 1 and collect Ball 3;
  • spend 1 second to return to the coordinate 0.

Here, we collected the balls in a non-descending order of their IDs: 1, 2, 2, 3, 3.

Sample Input 2

9
5 5
-4 4
4 3
6 3
-5 5
-3 2
2 2
3 3
1 4

Sample Output 2

38