分数: 525 点
问题陈述
具有生命值的怪物 H 已经出现在你的面前,回合制战斗已经开始。
每回合 1,2,…,你施放其中之一 N 咒语,咒语 1,…,N.
如果你施展法术 依次 i 反过来 j,怪物的生命值减少 每回合 d_i 每回合 j,j+1,…,j+t_i -1.
找到最早可以恢复怪物生命值的回合 0 或更少。
约束
- 1 \leq N \leq 3 \times 10^5
- 1 \leq H \leq 10^{18}
- 1 \leq t_i,d_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N H t_1 d_1 \vdots t_N d_N
输出
打印答案。
示例输入 1
2 20 2 2 5 1
示例输出 1
6
以下程序使怪物的生命值 0 以内依次 6,这是最早的。
- 施展法术 1 反过来 1。由于依次施放咒语 1,怪物的生命值减少 每回合 2 并变为 18.
- 施展法术 2 反过来 2。由于咒语是轮流施放的 1 和 2,怪物的生命值减少 每回合 2+1=3 并变为 15.
- 施展法术 1 反过来 3。由于咒语是轮流施放的 2 和 3,怪物的生命值减少 每回合 1+2=3 并变为 12.
- 施展法术 2 反过来 4。由于咒语是轮流施放的 2,3 和 4,怪物的生命值减少 每回合 1+2+1=4 并变为 8.
- 施展法术 1 反过来 5。由于咒语是轮流施放的 2,4 和 5,怪物的生命值减少 每回合 1+1+2=4 并变为 4.
- 施展法术 2 反过来 6。由于咒语是轮流施放的 2,4,5 和 6,怪物的生命值减少 每回合 1+1+2+1=5 并变为 -1.
示例输入 2
10 200 1 21 1 1 1 1 8 4 30 1 3 1 10 2 8 1 9 1 4 4
示例输出 2
9