当前没有测试数据。

F - 时间伤害

得分: $525$ 分

问题描述

在你面前出现了一个拥有 $H$ 生命值的怪物，一个回合制战斗开始了。

在每个回合 $1,2,…$ 中，你可以施放 $N$ 个法术，编号为 $1,…,N$。

如果在第 $j$ 回合施放第 $i$ 个法术，那么怪物在第 $j,j+1,…,j+t_i － 1$ 回合中的生命值都会减少 $d_i$。

请找出能将怪物的生命值降低到 $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$

输出

输出答案。

2 20
2 2
5 1

6

在回合 $6$，你可以按照以下步骤将怪物的生命值降低到 $0$ 或以下：

• 在回合 $1$ 施放法术 $1$，怪物的生命值降低 $2$ 变为 $18$。
• 在回合 $2$ 施放法术 $2$，由于回合 $1$ 和回合 $2$ 的法术，怪物的生命值降低 $2+1=3$ 变为 $15$。
• 在回合 $3$ 施放法术 $1$，由于回合 $2$ 和回合 $3$ 的法术，怪物的生命值降低 $1+2=3$ 变为 $12$。
• 在回合 $4$ 施放法术 $2$，由于回合 $2,3$ 和回合 $4$ 的法术，怪物的生命值降低 $1+2+1=4$ 变为 $8$。
• 在回合 $5$ 施放法术 $1$，由于回合 $2,4$ 和回合 $5$ 的法术，怪物的生命值降低 $1+1+2=4$ 变为 $4$。
• 在回合 $6$ 施放法术 $2$，由于回合 $2,4,5$ 和回合 $6$ 的法术，怪物的生命值降低 $1+1+2+1=5$，最终变为 $-1$。

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

9