AT_iroha2019_day4_b 叫び声

[problemUrl]: https://atcoder.jp/contests/iroha2019-day4/tasks/iroha2019_day4_b いろはちゃんのいる町には \\(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\\) に着く最速の時刻を求めよ。

入力は以下の形式で与えられる。 ``` \(N\) \(M\) \(L\) \(A_1\) \(B_1\) \(A_2\) \(B_2\) : \(A_N\) \(B_N\) ```

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

### ストーリー 闇をつんざくような叫び声。僕もいろはちゃんもすぐに外の様子に気がついた。遠くの街のほうが赤く光って、異音を轟かせながら揺れる。「あれって…！」僕が"それ"に気がついたときには、いろはちゃんはもう走り出していた。 ### 制約 - 入力はすべて整数 - \\(1≦N≦10^5\\) - \\(1≦M, L≦3\\times10^8\\) - \\(0≦A\_i≦10^{17}\\) - \\(1≦B\_i≦3\\times10^8\\) ### 解説 [解説](https://img.atcoder.jp/iroha2019-day4/editorial-B.pdf) ### Sample Explanation 1 次のように移動すると、駅 \\\\(M+1\\\\ (=4)\\\\) に時刻 \\\\(10\\\\) に着くことができる。 - 電車 \\\\(2\\\\) の出発を待つ ( 時刻 \\\\(0\\\\) - 時刻 \\\\(2\\\\) ) - 電車 \\\\(2\\\\) に乗って駅 \\\\(2\\\\) まで行く ( 時刻 \\\\(2\\\\) - 時刻 \\\\(5\\\\) ) - 電車 \\\\(1\\\\) を待つ ( 時刻 \\\\(5\\\\) - 時刻 \\\\(6\\\\) ) - 電車 \\\\(1\\\\) に乗って駅 \\\\(4\\\\) まで行く ( 時刻 \\\\(6\\\\) - 時刻 \\\\(10\\\\) ) ### Sample Explanation 2 次のように移動すると、駅 \\\\(M+1\\\\ (=4)\\\\) に時刻 \\\\(9\\\\) に着くことができる。 - 駅 \\\\(4\\\\) まで走る ( 時刻 \\\\(0\\\\) - 時刻 \\\\(9\\\\) ) ### Sample Explanation 3 次のように移動すると、駅 \\\\(M+1\\\\ (=101)\\\\) に時刻 \\\\(200\\\\) に着くことができる。 - 駅 \\\\(2\\\\) まで走る ( 時刻 \\\\(0\\\\) - 時刻 \\\\(10\\\\) ) - 駅 \\\\(1\\\\) まで走る ( 時刻 \\\\(10\\\\) - 時刻 \\\\(20\\\\) ) - 駅 \\\\(4\\\\) まで走る ( 時刻 \\\\(20\\\\) - 時刻 \\\\(50\\\\) ) - 駅 \\\\(4\\\\) で \\\\(20\\\\) 単位時間留まる ( 時刻 \\\\(50\\\\) - 時刻 \\\\(70\\\\) ) - 駅 \\\\(1\\\\) まで走る ( 時刻 \\\\(70\\\\) - 時刻 \\\\(100\\\\) ) - 電車 \\\\(1\\\\) に乗って駅 \\\\(101\\\\) まで行く ( 時刻 \\\\(100\\\\) - 時刻 \\\\(200\\\\) )