LHX 正在和一只怪物战斗。

怪物的血量值是 H 。

LHX 可以施放 N 种咒语。施放第 i 种咒语会使怪物的生命值降低 A_i ，代价是消耗 B_i 点魔法值。同一个咒语可以施放多次。除了咒语之外，没有其他方法可以降低怪物的生命值。

当怪物的生命值变为 0 或低于 0 时，LHX获胜。

找出获胜前必须消耗的最少魔法点数。

输入的内容为以下格式。
H   N
A₁ B₁
. . . .
. . . .
A_N B_N 

1 ≤ H ≤ 10⁴
1 ≤ N ≤ 10³
1 ≤ Ai ≤ 10⁴
1 ≤ Bi ≤ 10⁴
所有输入值均为整数。

输出获胜前必须消耗的最少魔法点数。

首先，让我们施放第一个魔法，降低怪物的生命值 8 ，代价是 3 魔法点数。现在怪物的生命值是 1 。

然后，施放第三个魔法，降低怪物生命值 2 ，消耗 1 魔力值。怪物的生命值现在是 −1 。

这样，我们就能以总计 4 点魔法值的代价获得胜利。


可以发现这是获胜的最小代价。

大数据与人工智能学院2023级ACM集训队选拔赛（1）