Crested Ibis vs Monster

题目描述

Ibis 正在与一只怪物战斗。 怪物的 生命值 为 $H$。 Ibis 可以使用 $N$ 种魔法。施放第 $i$ 种魔法会以 $B_i$ 点魔力为代价，使怪物的生命值减少 $A_i$。 同一种魔法可以施放多次。没有其他方法可以减少怪物的生命值。 当怪物的生命值变为 $0$ 或更低时，Ibis 获胜。 求取胜前必须消耗的最小魔力总和。

输入格式

输入从标准输入按以下格式给出： $H$ $N$ $A_1$ $B_1$ $:$ $A_N$ $B_N$

输出格式

输出取胜前必须消耗的最小魔力总和。

9 3
8 3
4 2
2 1

4

100 6
1 1
2 3
3 9
4 27
5 81
6 243

100

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

139815

提示

$1 \leq H \leq 10^4$ $1 \leq N \leq 10^3$ $1 \leq A_i \leq 10^4$ $1 \leq B_i \leq 10^4$ 输入中的所有数值均为整数。首先，施放第一种魔法一次，使怪物的生命值减少 $8$，消耗 $3$ 点魔力。怪物的生命值现在为 $1$。 然后，施放第三种魔法一次，使生命值减少 $2$，消耗 $1$ 点魔力。怪物的生命值现在为 $-1$。 以这种方式，我们可以以总消耗 $4$ 点魔力获胜。
最优的方案是施放第一种魔法 $100$ 次。

标签: AtCoder|abc153E

来源

AtCoder|abc153E