103107: [Atcoder]ABC310 Ex - Negative Cost
Description
Score : $625$ points
Problem Statement
A monster with health $H$ has appeared right in front of you. Your magic power is now $0$.
You can use $N$ moves called move $1$, move $2$, $\ldots$, move $N$, any number of times in any order.
For each $i = 1, 2, \ldots, N$, move $i$ can only be used when your magic power is at least $C_i$, and its use will decrease your magic power by $C_i$ and the monster's health by $D_i$. Here, if $C_i$ is negative, decreasing your magic power by $C_i$ means increasing it by $-C_i$.
Find the minimum possible number of times you use moves before the monster's health is $0$ or lower. The constraints of this problem guarantee that a finite number of uses of moves can make it $0$ or lower (see below).
Constraints
- $1 \leq N \leq 300$
- $1 \leq H \leq 10^{18}$
- $-300 \leq C_i \leq 300$
- $C_i \leq 0$ for some $1 \leq i \leq N$.
- $1 \leq D_i \leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $H$ $C_1$ $D_1$ $C_2$ $D_2$ $\vdots$ $C_N$ $D_N$
Output
Print the answer.
Sample Input 1
3 48 3 20 -4 2 1 5
Sample Output 1
5
From the initial state where your magic power is $0$ and the monster's health is $48$, consider using moves as follows.
- Use move $2$. Now, your magic power is $4$, and the monster's health is $46$.
- Use move $3$. Now, your magic power is $3$, and the monster's health is $41$.
- Use move $1$. Now, your magic power is $0$, and the monster's health is $21$.
- Use move $2$. Now, your magic power is $4$, and the monster's health is $19$.
- Use move $1$. Now, your magic power is $1$, and the monster's health is $-1$.
Here, you use moves five times before the monster's health is not greater than $0$, which is the minimum possible number.
Sample Input 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
Sample Output 2
595990842
Input
题意翻译
## 题目描述 一头怪兽挡在你的面前，它有 $H$ 的血量。 你有 $n$ 种技能，每个技能都可以**以任意合法顺序无限次使用**。 你有一个魔力值，初始为 $0$ 。 第 $i$ 种技能会消耗 $C_i$ 的魔力值，并对怪兽造成 $D_i$ 的伤害。你要时刻保证魔力值非负。 特别的， $C_i$ 可能为负数，此时该技能会增加 $-C_i$ 的魔力值。 当怪物血量不为正数时，怪物就死了。 问：最少发动多少次技能，能杀死这只怪物？ ## 输入格式 第一行 $2$ 个整数 $n,H$ 。 接下来 $n$ 行每行 $2$ 个整数 $C_i,D_i$ 。 ## 输出格式 一行一个正整数表示答案。 ## 说明/提示 对于所有的数据： - $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$ - 所有输入均为整数。 ### 样例 1 说明 分别使用技能 $2,3,1,2,1$ ，共 $5$ 次技能。可以证明这是最小的。Output
问题描述
一只生命值为$H$的怪物出现在你的面前。你的魔力值现在是$0$。
你可以按照任意顺序使用任意次数的$N$种移动方式，称为移动$1$，移动$2$，$\ldots$，移动$N$。
对于每个$i=1,2,\ldots,N$，当你的魔力值至少为$C_i$时，才能使用移动$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$
- 对于某个$1 \leq i \leq N$，$C_i \leq 0$。
- $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$之前，你使用了$5$次移动，这是可能的最小次数。
样例输入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