2436: LHX打怪兽Ⅱ
[Creator : ]
Description
LHX 正在和一只怪物战斗。
怪物的血量值是 H 。
LHX 可以施放 N 种咒语。施放第 i 种咒语会使怪物的生命值降低 Ai ，代价是消耗 Bi 点魔法值。同一个咒语可以施放多次。除了咒语之外，没有其他方法可以降低怪物的生命值。
当怪物的生命值变为 0 或低于 0 时，LHX获胜。
找出获胜前必须消耗的最少魔法点数。
怪物的血量值是 H 。
LHX 可以施放 N 种咒语。施放第 i 种咒语会使怪物的生命值降低 Ai ，代价是消耗 Bi 点魔法值。同一个咒语可以施放多次。除了咒语之外，没有其他方法可以降低怪物的生命值。
当怪物的生命值变为 0 或低于 0 时，LHX获胜。
找出获胜前必须消耗的最少魔法点数。
Input
输入的内容为以下格式。
H N
A1 B1
. . . .
. . . .
AN BN
1 ≤ H ≤ 104
1 ≤ N ≤ 103
1 ≤ Ai ≤ 104
1 ≤ Bi ≤ 104
所有输入值均为整数。
H N
A1 B1
. . . .
. . . .
AN BN
1 ≤ H ≤ 104
1 ≤ N ≤ 103
1 ≤ Ai ≤ 104
1 ≤ Bi ≤ 104
所有输入值均为整数。
Output
输出获胜前必须消耗的最少魔法点数。
Sample Input Copy
9 3
8 3
4 2
2 1
Sample Output Copy
4
HINT
首先，让我们施放第一个魔法，降低怪物的生命值 8 ，代价是 3 魔法点数。现在怪物的生命值是 1 。
然后，施放第三个魔法，降低怪物生命值 2 ，消耗 1 魔力值。怪物的生命值现在是 −1 。
这样，我们就能以总计 4 点魔法值的代价获得胜利。
可以发现这是获胜的最小代价。
然后，施放第三个魔法，降低怪物生命值 2 ，消耗 1 魔力值。怪物的生命值现在是 −1 。
这样，我们就能以总计 4 点魔法值的代价获得胜利。
可以发现这是获胜的最小代价。