013 - いちご (Strawberry)

問題文

Just Oishi Ichigo 農園 (以下 JOI 農園) は東西に細長いことで有名ないちご農園であり，その入り口は農園の最も西にある．以下では，入り口から東に k メートル進んだ場所を地点 k と呼ぶことにする．

JOI 農園内には N 個のいちごがなっている．それぞれ 1 から N の番号がつけられている．どのいちごも時刻 0 までは青い．いちご i (1 ≤ i ≤ N) は地点 A_i に実をつけており，時刻 T_i になると熟し赤い状態になる．

いちごは青い状態では収穫できない．つまり，いちご i は時刻 T_i となるまで収穫できない．あなたは時刻 0 に地点 0 にある農園の入り口から出発して，最大秒速 1 メートルで東西方向に移動しながらいちごを収穫する．いちごを収穫するのにかかる時間は無視できるとする．

いちご農園についての情報が与えられるので，すべてのいちごを赤い状態で収穫したあと入り口に帰ってくるまでにかかる時間の最小値を求めるプログラムを作成せよ．

制約

• 1 ≤ N ≤ 100,000．
• 0 ≤ A_i ≤ 1,000,000,000 (=10⁹) (1 ≤ i ≤ N)．
• 0 ≤ T_i ≤ 1,000,000,000 (=10⁹) (1 ≤ i ≤ N)．
• 入力される値はすべて整数である．

入力

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

N
A_1 T_1
A_2 T_2
.
.
.
A_N T_N

出力

すべてのいちごを赤い状態で収穫したあと入り口に帰ってくるまでにかかる時間の最小値を 1 行に出力せよ．

入力例 1

10
1 3
2 1
3 4
4 1
5 5
6 9
7 2
8 6
9 5
10 3

出力例 1

20

はじめの 10 秒かけて地点 10 まで移動すると，その道中でいちご 2, 4, 5, 7, 8, 9, 10 をこの順に収穫することができる．その後 10 秒かけて地点 0 まで戻ると，その道中でいちご 6, 3, 1 をこの順に収穫することができる．これで 10 個すべてのいちごを赤い状態で収穫することができる．

入力例 2

10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45

出力例 2

450

以下のように移動すると 450 秒ですべてのいちごを赤い状態で収穫できる．

1. 45 秒かけて地点 45 まで移動する．このとき時刻 45 なのでいちご 10 を収穫できる．収穫後 45 秒かけて地点 0 まで移動する．
2. その後，40 秒かけて地点 40 まで移動する．このとき時刻 130 なのでいちご 9 を収穫できる．収穫後 40 秒かけて地点 0 まで移動する．
3. その後，35 秒かけて地点 35 まで移動する．このとき時刻 205 なのでいちご 8 を収穫できる．収穫後 35 秒かけて地点 0 まで移動する．
4. その後，30 秒かけて地点 30 まで移動する．このとき時刻 270 なのでいちご 7 を収穫できる．収穫後 30 秒かけて地点 0 まで移動する．
5. その後，25 秒かけて地点 25 まで移動する．このとき時刻 325 なのでいちご 6 を収穫できる．収穫後 25 秒かけて地点 0 まで移動する．
6. その後，20 秒かけて地点 20 まで移動する．このとき時刻 370 なのでいちご 5 を収穫できる．収穫後 20 秒かけて地点 0 まで移動する．
7. その後，15 秒かけて地点 15 まで移動する．このとき時刻 405 なのでいちご 4 を収穫できる．収穫後 15 秒かけて地点 0 まで移動する．
8. その後，10 秒かけて地点 10 まで移動する．このとき時刻 430 なのでいちご 3 を収穫できる．収穫後 10 秒かけて地点 0 まで移動する．
9. その後，5 秒かけて地点 5 まで移動する．このとき時刻 445 なのでいちご 2 を収穫できる．収穫後 5 秒かけて地点 0 まで移動する．
10. ちょうど時刻 450 に地点 0 に到達するので，いちご 1 を収穫できる．すべてのいちごを収穫すると同時に地点 0 に到着した．

入力例 3

15
11 23
3 94
89 3
38 58
65 29
41 3
80 42
22 76
48 85
83 98
87 29
97 96
22 75
57 25
99 33

出力例 3

198