题目描述

小k正在和一只怪物战斗，怪物的生命值是 $H$ 。

小k可以施放 $N$ 种咒语。施放第 $i$ 种咒语会使怪物的生命值降低 $A_i$ ，同时消耗 $B_i$ 点魔法值。

同一个咒语可以施放多次。除了咒语之外，没有其他方法可以降低怪物的生命值。

当怪物的生命值 $<=0$ 时获胜，请帮小k找出获胜必须消耗的最少魔法点数。

输入格式

$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$ 点魔法值的代价获得胜利，没有比这更低的消耗了。

数据规模与约定

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