AT_abc303_f [ABC303F] Damage over Time

题目描述

你面前出现了一只体力为 $H$ 的怪物，回合制战斗开始了。

你可以在每个回合 $1,2,\ldots$ 中，从 $N$ 种咒文 $1,\ldots,N$ 中选择一种施放。

在第 $i$ 回合施放第 $j$ 种咒文时，该咒文的效果会使怪物在第 $i,i+1,\ldots,i+t_j-1$ 回合的每一回合体力减少 $d_j$。

请你求出最早能将怪物体力降至 $0$ 或以下的回合数。

输入格式

输入以如下格式从标准输入给出。

$N$ $H$
$t_1$ $d_1$
$\vdots$
$t_N$ $d_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 20
2 2
5 1

输出 #1

6

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq H \leq 10^{18}$
• $1 \leq t_i, d_i \leq 10^9$
• 输入均为整数

样例解释 1

如下操作可以在第 $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$。

由 ChatGPT 4.1 翻译