朱鹮与怪物

题目描述

朱鹮正在与怪物战斗。

怪物的体力为 $H$。

朱鹮可以使用 $N$ 种魔法,使用第 $i$ 种魔法可以减少怪物的 $A_i$ 点体力,但会消耗朱鹮的 $B_i$ 点魔力。

同一种魔法可以重复使用任意多次。除了魔法之外,没有其他方法可以减少怪物的体力。

当怪物的体力降到 $0$ 以下(含)时,朱鹮获胜。

求朱鹮击败怪物所消耗的魔力总和的最小值。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出朱鹮击败怪物所消耗的魔力的最小值。

样例

9 3
8 3
4 2
2 1

4

首先使用第 $1$ 种魔法,消耗朱鹮 $3$ 点魔力,减少怪物 $8$ 点体力。怪物的体力变为 $1$。

接着使用第 $3$ 种魔法,消耗朱鹮 $1$ 点魔力,减少怪物 $2$ 点体力。怪物的体力变为 $-1$。

这样,朱鹮消耗的魔力总和为 $4$。

100 6
1 1
2 3
3 9
4 27
5 81
6 243

100

使用第 $1$ 种魔法 $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$
• 输入中的所有值都是整数。