B - 叫び声 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(400\) 点

ストーリー

闇をつんざくような叫び声。僕もいろはちゃんもすぐに外の様子に気がついた。遠くの街のほうが赤く光って、異音を轟かせながら揺れる。「あれって…！」僕が"それ"に気がついたときには、いろはちゃんはもう走り出していた。

問題文

いろはちゃんのいる町には \(M+1\) 個の駅と \(N\) 個の電車があり、それぞれ \(1\) から \(M+1\)、\(1\) から \(N\) の番号が付けられている。

現在の時刻は \(0\) である。今いろはちゃんは駅 \(1\) におり、駅 \(M+1\) に行こうとしている。

電車 \(i\) は時刻 \(A_i\) に駅 \(1\) を出発し、駅 \(j+1\ (1≦j≦M)\) には時刻 \(A_i+B_i\times j\) に着く。

また、いろはちゃんは走ることで駅 \(k\ (1≦k≦M)\) と駅 \(k+1\) の間を \(L\) 単位時間かけて移動できる。

いろはちゃんは駅で移動手段を変えることができ、これにかかる時間は無視できる。駅以外の場所で移動手段を変えることはできない。

いろはちゃんが駅 \(M+1\) に着く最速の時刻を求めよ。

制約

  • 入力はすべて整数
  • \(1≦N≦10^5\)
  • \(1≦M, L≦3\times10^8\)
  • \(0≦A_i≦10^{17}\)
  • \(1≦B_i≦3\times10^8\)

入力

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

\(N\) \(M\) \(L\)
\(A_1\) \(B_1\)
\(A_2\) \(B_2\)
:
\(A_N\) \(B_N\)

出力

答えを \(1\) 行に出力し、最後に改行せよ。

入力例 1

3 3 4
4 2
2 3
3 4

出力例 1

10

次のように移動すると、駅 \(M+1\ (=4)\) に時刻 \(10\) に着くことができる。

  • 電車 \(2\) の出発を待つ ( 時刻 \(0\) - 時刻 \(2\) )
  • 電車 \(2\) に乗って駅 \(2\) まで行く ( 時刻 \(2\) - 時刻 \(5\) )
  • 電車 \(1\) を待つ ( 時刻 \(5\) - 時刻 \(6\) )
  • 電車 \(1\) に乗って駅 \(4\) まで行く ( 時刻 \(6\) - 時刻 \(10\) )

入力例 2

3 3 3
4 2
2 3
3 4

出力例 2

9

次のように移動すると、駅 \(M+1\ (=4)\) に時刻 \(9\) に着くことができる。

  • 駅 \(4\) まで走る ( 時刻 \(0\) - 時刻 \(9\) )

入力例 3

1 100 10
100 1

出力例 3

200

次のように移動すると、駅 \(M+1\ (=101)\) に時刻 \(200\) に着くことができる。

  • 駅 \(2\) まで走る ( 時刻 \(0\) - 時刻 \(10\) )
  • 駅 \(1\) まで走る ( 時刻 \(10\) - 時刻 \(20\) )
  • 駅 \(4\) まで走る ( 時刻 \(20\) - 時刻 \(50\) )
  • 駅 \(4\) で \(20\) 単位時間留まる ( 時刻 \(50\) - 時刻 \(70\) )
  • 駅 \(1\) まで走る ( 時刻 \(70\) - 時刻 \(100\) )
  • 電車 \(1\) に乗って駅 \(101\) まで行く ( 時刻 \(100\) - 時刻 \(200\) )

入力例 4

3 139128390 220019821
3162336416461334 196423673
2909210940940890 272140126
31923189201903829 68312342

出力例 4

30490445798837804

解説

解説