题目描述

题目大意

$Ibis$ 在打怪，这只怪的血量为 $H$ 。

他可以念 $N$ 种咒语，第 $i$ 种会对怪兽造成 $A_i$ 点伤害，但是会消耗 $B_i$ 点魔法点数。每一种咒语可以念多次。

当怪兽血量 $H \le 0$ 时，$Ibis$ 就获胜了。

请求出 $Ibis$ 在击败怪兽的情况下，所消耗的魔法点数的最小值。

输入

输入两个整数表示$H,N$

接下来一共$N$行，表示$A_i,B_i$

输出

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

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

提示

• $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$