레이팅 미적용설명
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 9 ) ( 1 ≦ i ≦ N ).
0 ≦ T i ≦ 1 000 000 000 (= 10 9 ) ( 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
출력
20
예제 2
입력
10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45
출력
450
예제 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
출력
198
문제 정보