← 返回题目列表

AtCoder · abc303_f

I. 随着时间的推移造成的损害

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

分数: 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