AT_abc310_h.[ABC310Ex] Negative Cost

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入#1
```
3 48
3 20
-4 2
1 5
```
输出#1
```
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

说明/提示

对于所有的数据：

$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$ 次技能。可以证明这是最小的。

输入解题思路，AI测评打分。不知道怎么写?

首页