Damage over Time

题目描述

一个生命值为 $H$ 的怪物出现在你面前，回合制战斗开始。 在每个回合 $1,2,\dots$，你施放 $N$ 个法术中的一个，法术为 $1,\dots,N$。 如果你在回合 $j$ 施放了法术 $i$，则在回合 $j,j+1,\dots,j+t_i-1$ 每一回合怪物的生命值都会减少 $d_i$。 求你最早可以使怪物的生命值变为 $0$ 或更少的回合数。

输入格式

输入从标准输入按以下格式给出： $N$ $H$ $t_1$ $d_1$ $\vdots$ $t_N$ $d_N$

输出格式

输出答案。

2 20
2 2
5 1

6

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

9

提示

$1 \leq N \leq 3 \times 10^5$ $1 \leq H \leq 10^{18}$ $1 \leq t_i,d_i \leq 10^9$ 输入中的所有数值均为整数。下面的操作可以在第 $6$ 回合使怪物的生命值变为 $0$ 或更少，这是最早的。

在第 $1$ 回合施放法术 $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$。

标签: AtCoder|abc303F

来源

AtCoder|abc303F