题目描述

Ibis正在与一只怪物战斗。

怪物的生命值为$H$。

Ibis可以释放$N$种法术。第$i$种法术能够将怪物的生命值减少$A_i$，但需要消耗$B_i$点魔法值。

可以重复使用同一种法术。除了法术外，没有其他方式可以减少怪物的生命值。

当怪物的生命值变为$0$或更低时，Ibis获胜。

求在获胜之前最少需要消耗的总魔法值。

约束条件

• $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$
• 输入中的所有值都是整数。

输入

从标准输入读入数据，格式如下：

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

输出

打印在获胜之前最少需要消耗的总魔法值。

示例输入 1

9 3
8 3
4 2
2 1

示例输出 1

4

首先，我们使用第一种法术来将怪物的生命值减少$8$，消耗$3$点魔法值。怪物的生命值现在是$1$。

然后，使用第三种法术来将怪物的生命值减少$2$，消耗$1$点魔法值。怪物的生命值现在是$-1$。

这样，我们可以在总共消耗$4$点魔法值的情况下获胜。

示例输入 2

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

示例输出 2

100

最佳策略是连续施放第一种法术$100$次。

示例输入 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

示例输出 3

139815