← 返回题目列表

AtCoder · abc310_h

Ex. 负成本

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

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