题目描述

トキはモンスターと戦っています。

モンスターの体力は $H$ です。

トキは $N$ 種類の魔法が使え、$i$ 番目の魔法を使うと、モンスターの体力を $A_i$ 減らすことができますが、トキの魔力を $B_i$ 消耗します。

同じ魔法は何度でも使うことができます。魔法以外の方法でモンスターの体力を減らすことはできません。

モンスターの体力を $0$ 以下にすればトキの勝ちです。

トキがモンスターに勝つまでに消耗する魔力の合計の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $N$ $A_1$ $B_1$ $:$ $A_N$ $B_N$

输出格式

トキがモンスターに勝つまでに消耗する魔力の最小値を出力せよ。

题目大意

$Ibis$ 在打怪，这只怪的血量为 $H$ 。
他可以念 $N$ 种咒语，第 $i$ 种会对怪兽造成 $A_i$ 点伤害，但是会消耗 $B_i$ 点魔法点数。每一种咒语可以念多次。
当怪兽血量 $H \le 0$ 时，$Ibis$ 就获胜了。
请求出 $Ibis$ 在击败怪兽的情况下，所消耗的魔法点数的最小值。

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$
• 入力中のすべての値は整数である。

Sample Explanation 1

最初に $1$ 番目の魔法を使い、トキの魔力を $3$ 消耗して、モンスターの体力を $8$ 減らします。モンスターの体力は $1$ になります。 次に $3$ 番目の魔法を使い、トキの魔力を $1$ 消耗して、モンスターの体力を $2$ 減らします。モンスターの体力は $-1$ になります。 これにより、トキが消耗した魔力の合計は $4$ になります。

Sample Explanation 2

$1$ 番目の魔法を $100$ 回使うのが最適です。