AT_abc310_h [ABC310Ex] Negative Cost

题目描述

一头怪兽挡在你的面前，它有 $H$ 的血量。

你有 $n$ 种技能，每个技能都可以以任意合法顺序无限次使用。

你有一个魔力值，初始为 $0$ 。

第 $i$ 种技能会消耗 $C_i$ 的魔力值，并对怪兽造成 $D_i$ 的伤害。你要时刻保证魔力值非负。

特别的， $C_i$ 可能为负数，此时该技能会增加 $-C_i$ 的魔力值。

当怪物血量不为正数时，怪物就死了。

问：最少发动多少次技能，能杀死这只怪物？

输入格式

第一行 $2$ 个整数 $n,H$ 。

接下来 $n$ 行每行 $2$ 个整数 $C_i,D_i$ 。

输出格式

一行一个正整数表示答案。

输入输出样例 #1

输入 #1

3 48
3 20
-4 2
1 5

输出 #1

5

输入输出样例 #2

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

说明/提示

对于所有的数据：

• $1\le n \le 300$
• $1\le H \le 10^{18}$
• $-300 \le C_i \le 300$
• $\exist C_i <0$
• $1\le D_i \le 10^9$
• 所有输入均为整数。

分别使用技能 $2,3,1,2,1$ ，共 $5$ 次技能。可以证明这是最小的。