Skip to content
Sign in

いちご (Strawberry)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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

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

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

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

Constraints

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

Input

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

\(N\)
\(A_1\) \(T_1\)
\(A_2\) \(T_2\)
\(\vdots\)
\(A_N\) \(T_N\)

Output

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

Examples

Sample input 1
10
1 3
2 1
3 4
4 1
5 5
6 9
7 2
8 6
9 5
10 3
Sample output 1
20

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

Sample input 2
10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45
Sample output 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\) に到着した．
Sample input 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
Sample output 3
198

Notes

JOI 2020 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source