トキ正在与怪物战斗。

怪物的体力为 $H$。

トキ可以使用 $N$ 种不同的魔法，第 $i$ 种魔法可以使怪物的体力减少 $A_i$，但会消耗トキ $B_i$ 的魔力。

每种魔法可以使用任意多次。除了魔法，无法通过其他方式减少怪物的体力。

只要怪物的体力降到 $0$ 或以下，トキ就算获胜。

请你求出トキ在打败怪物前所需消耗的最小魔力总和。

输入格式

输入通过标准输入给出，格式如下：

$H$ $N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$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$
• 输入中的所有数值均为整数。

样例解释 1

首先使用第 $1$ 种魔法，トキ消耗 $3$ 点魔力，将怪物体力减少 $8$，怪物体力变为 $1$。
接着使用第 $3$ 种魔法，トキ消耗 $1$ 点魔力，将怪物体力减少 $2$，怪物体力变为 $-1$。
这样，トキ总共消耗了 $4$ 点魔力。

样例解释 2

最优做法是使用第 $1$ 种魔法 $100$ 次。