负代价

题目描述

一头生命值为 $H$ 的怪物出现在你面前。 你当前的魔力为 $0$。

你可以任意次数、以任意顺序使用称为招式 1、招式 2、$\ldots$、招式 $N$ 的 $N$ 种招式。

对于每个 $i = 1, 2, \ldots, N$,招式 $i$ 只能在魔力至少为 $C_i$ 时使用,使用后魔力减少 $C_i$,怪物生命值减少 $D_i$。 这里,如果 $C_i$ 为负数,那么魔力减少 $C_i$ 意味着魔力增加 $-C_i$。

求在怪物生命值降到 $0$ 或以下之前,最少需要使用招式的次数。 该问题的约束保证了使用有限次招式可以使怪物生命值降到 $0$ 或以下。

输入格式

输入按以下格式从标准输入给出:

$N$ $H$
$C_1$ $D_1$
$C_2$ $D_2$
$\vdots$
$C_N$ $D_N$

输出格式

输出答案。

样例

3 48
3 20
-4 2
1 5

5

从魔力为 $0$、怪物生命值为 $48$ 的初始状态出发,考虑如下使用招式。

使用招式 2。现在,魔力为 $4$,怪物生命值为 $46$。

使用招式 3。现在,魔力为 $3$,怪物生命值为 $41$。

使用招式 1。现在,魔力为 $0$,怪物生命值为 $21$。

使用招式 2。现在,魔力为 $4$,怪物生命值为 $19$。

使用招式 1。现在,魔力为 $1$,怪物生命值为 $-1$。

这里,在怪物生命值不大于 $0$ 之前使用了 5 次招式,这是最少的使用次数。

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

595990842

数据范围

• $1 \le N \le 300$
• $1 \le H \le 10^{18}$
• $-300 \le C_i \le 300$
• 存在某个 $1 \le i \le N$ 使得 $C_i \le 0$。
• $1 \le D_i \le 10^9$
• 输入中的所有值均为整数。