题目描述：

芳芳在与怪物战斗，怪物初始生命值为 H。芳芳有 N 种法术，第 i 种法术对怪物造成 Aᵢ 点伤害，消耗 Bᵢ 点魔力。每种法术可以重复施放任意次，且只能靠法术使生命值下降；当怪物生命值变为 0 或以下时芳芳获胜。要求在胜利前消耗的最少总魔力。

输入格式：

第一行为 H N，接下来的 N 行每行两个整数 Aᵢ Bᵢ (i = 1, …, N)。

输出格式：

一个整数，表示达成胜利所需的最小总魔力。

样例：

9 3
8 3
4 2
2 1

4

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

139815

样例 1 说明：

首先，施展第一个魔法将怪物的生命值减少 8 点，消耗 3 点魔法值。此时怪物的生命值为 1；然后，施展第三个魔法将怪物的生命值减少 2 点，消耗 1 点魔法值。此时怪物的生命值为 -1。

通过这种方式，我们可以以总共 4 点魔法值的代价获胜。

数据范围：

• 1 ≤ H ≤ 10⁴

• 1 ≤ N ≤ 10³

• 1 ≤ Aᵢ, Bᵢ ≤ 10⁴

• 所有输入均为整数。