配点 : $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$

出力

答え [秒] を出力せよ。

5
2 2
3 1
1 3
4 2
5 3

12

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

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

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

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

38