E - 绿牛对战怪物

得分：500分

题目描述

绿牛正在和怪物战斗。

怪物的初始生命值为$H$。

绿牛可以施放$N$种法术。第$i$种法术会使怪物生命值减少$A_i$，代价是$B_i$点魔法值。

同一法术可以施放多次。除了施放法术以外，没有其他方式可以减少怪物的生命值。

绿牛在怪物的生命值降至$0$或以下时获胜。

求获胜之前所需的最少总魔法值消耗。

约束

• $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$
• 输入的所有数值均为整数。

输入

输入的数据从标准输入中读取，格式如下：

$H$ $N$

$A_1$ $B_1$

$:$

$A_N$ $B_N$

输出

输出获胜之前所需的最少总魔法值消耗。

9 3
8 3
4 2
2 1

4

首先，使用第一种法术降低怪物的生命值$8$，消耗$3$点魔法值。怪物的生命值变为$1$。

然后，使用第三种法术降低怪物的生命值$2$，消耗$1$点魔法值。怪物的生命值变为$-1$。

这样，我们可以以总消耗$4$点魔法值取胜。

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

100

将第一种法术施放$100$次是最优的。

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

139815