← 返回题目列表

AtCoder · iroha2019_day4_b

B. 尖叫

中文机器翻译题面 查看原题

配点 : \(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

解説

解説