分数: 625 点
问题陈述
具有生命值的怪物 H 已经出现在你的面前。 你的魔力现在 0.
您可以使用 N 移动称为移动 1,移动 2, \ldots,移动 N,按任意顺序任意次数。
对于每个 i = 1, 2, \ldots, N,移动 i 只有当你的魔力至少为 C_i,使用它会使你的魔法强度减少 C_i 和怪物的生命值 D_i。 在这里,如果 C_i 为负值,使你的魔力减少 C_i 意味着将其增加 -C_i.
求在怪物的生命值恢复之前你使用移动的最少可能次数 0 或更低。 这个问题的约束保证了有限次数的移动可以使它 0 或更低(见下文)。
约束
- 1 \leq N \leq 300
- 1 \leq H \leq 10^{18}
- -300 \leq C_i \leq 300
- C_i \leq 0 对于一些 1 \leq i \leq N.
- 1 \leq D_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N H C_1 D_1 C_2 D_2 \vdots C_N D_N
输出
打印答案。
示例输入 1
3 48 3 20 -4 2 1 5
示例输出 1
5
从你的魔力初始状态开始 0 怪物的生命值是 48,考虑使用如下移动。
- 使用移动 2。现在,你的魔力是 4,怪物的生命值为 46.
- 使用移动 3。现在,你的魔力是 3,怪物的生命值为 41.
- 使用移动 1。现在,你的魔力是 0,怪物的生命值为 21.
- 使用移动 2。现在,你的魔力是 4,怪物的生命值为 19.
- 使用移动 1。现在,你的魔力是 1,怪物的生命值为 -1.
在这里,在怪物的生命值不大于之前,你使用移动五次 0,这是可能的最小数字。
示例输入 2
20 583988303060450752 -64 273760634 -238 960719353 -114 191410838 -250 357733867 232 304621362 -286 644706927 210 37849132 -230 556412112 -142 136397527 101 380675202 -140 152300688 190 442931589 -187 940659077 -12 312523039 32 126515475 -143 979861204 105 488280613 240 664922712 290 732741849 69 541282303
示例输出 2
595990842