配点 : $700$ 点

問題文

高橋君と青木君は数直線と区間を使ってゲームをすることにしました。 高橋君は数直線上に立っており、最初は座標 $0$ にいます。 また、青木君は $N$ 個の区間を持っており、$i$ 個目の区間は $[L_i,R_i]$、つまり座標が $L_i$ 以上 $R_i$ 以下の点からなる区間となっています。

このゲームは $N$ 回のステップからなります。$i$ ステップ目では以下の手順を踏みます。

• まず青木君は、$N$ 個の区間の内、まだ選んでいない区間を一つ選び、その区間を高橋君に伝える。
• 次に高橋君は、青木君が今回選んだ区間に入るように、数直線上を移動する。

$N$ 回のステップを終えた後、高橋君が座標 $0$ まで戻ることでゲームは終了します。

高橋君がゲーム全体を通して移動する距離の合計を $K$ としたとき、青木君は $K$ ができるだけ大きくなるように区間を選び、 高橋君は $K$ ができるだけ小さくなるように移動します。 このとき、最終的に高橋君の移動距離の合計 $K$ はいくつになるでしょうか。

制約

• $1 \leq N \leq 10^5$
• $-10^5 \leq L_i < R_i \leq 10^5$
• $L_i$ と $R_i$ は整数

入力

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

$N$

$L_1$ $R_1$

:

$L_N$ $R_N$

出力

高橋君と青木君が上記の条件に従って行動するときの高橋君が動く距離の合計を、$1$ つの整数値として出力せよ。 ただし、$L_i,R_i$ が整数であるとき、$K$ が整数となることは保証されている。

3
-5 1
3 7
-4 -2

10

高橋君と青木君の行動の一例は以下のようになります。

• 青木君が $1$ 番目の区間を選び、高橋君は座標 $0$ から座標 $-4$ まで距離 $4$ だけ移動する。
• 青木君が $3$ 番目の区間を選び、高橋君は座標 $-4$ のまま動かない
• 青木君が $2$ 番目の区間を選び、高橋君は座標 $-4$ から座標 $3$ まで距離 $7$ だけ移動する。
• 高橋君は座標 $3$ から座標 $0$ まで距離 $3$ だけ移動する。

このとき高橋君の移動距離の合計は $14$ になってしまうので、高橋君の行動は最適ではないですが、 動き方を変えることで、移動距離の合計を $10$ にすることができます。

3
1 2
3 4
5 6

12

5
-2 0
-2 0
7 8
9 10
-2 -1

34