配点 : \(400\) 点
故事
一声刺穿黑暗的尖叫声。我和彩叶酱立即注意到了外面发生的事情。远处的城市发出红光,摇晃着,发出奇怪的声音。 “那是……!”当我注意到这一点时,彩叶酱已经开始奔跑了。
問題文
彩叶酱居住的小镇有\(M+1\)个车站和\(N\)趟车,每趟车的编号从\(1\)到\(M+1\),从\(1\)到\(N\)。
当前时间为 \(0\)。伊吕波目前位于车站\(1\),即将前往车站\(M+1\)。
火车\(i\)于时间\(A_i\)离开车站\(1\),并于时间\(A_i+B_i\times j\)到达车站\(j+1\(1≤j≤M)\)。
另外,通过跑步,彩羽酱可以在\(L\)单位时间内在车站\(k\(1≤k≤M)\)和车站\(k+1\)之间行驶。
彩叶酱可以在车站改变她的交通方式,而且所花费的时间可以忽略不计。车站以外的地方不能变更交通工具。
求 Iroha 到达车站的最快时间 \(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
通过如下移动,您可以在时间 \(10\) 到达车站 \(M+1\ (=4)\)。
- 等待火车\(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
通过如下移动,您可以在时间\(9\)到达车站\(M+1\(=4)\)。
- 运行到站 \(4\)(时间 \(0\) - 时间 \(9\))
入力例 3
1 100 10 100 1
出力例 3
200
通过如下移动,您可以在时间 \(200\) 到达车站 \(M+1\ (=101)\)。
- 运行到站\(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