E - 朱鹮与怪兽（Crested Ibis vs Monster）

**时间限制：**2 秒
**内存限制：**1024 MiB

题目描述

朱鹮正在与一只怪兽战斗。怪兽的生命值为 (H)。

朱鹮可以使用 (N) 种法术。使用第 (i) 种法术会使怪兽的生命值减少 (A_i)，并消耗 (B_i) 点魔法值。

每种法术都可以使用任意次。除了使用法术以外，没有其他方法可以降低怪兽的生命值。当怪兽的生命值降至 (0) 或以下时，朱鹮获胜。

请计算朱鹮获胜前至少需要消耗多少点魔法值。

输入格式

第一行包含两个整数 (H) 和 (N)，分别表示怪兽的生命值和法术种类数。

接下来 (N) 行，每行包含两个整数 (A_i) 和 (B_i)，表示第 (i) 种法术造成的伤害和消耗的魔法值。

输出格式

输出一个整数，表示朱鹮获胜前需要消耗的最少魔法值。

数据范围

• (1 \le H \le 10^4)
• (1 \le N \le 10^3)
• (1 \le A_i \le 10^4)
• (1 \le B_i \le 10^4)
• 输入中的所有数值均为整数。

样例 1

输入

9 3
8 3
4 2
2 1

输出

4

说明

先使用第 1 种法术，消耗 3 点魔法值，使怪兽生命值减少 8，剩余生命值为 1。

再使用第 3 种法术，消耗 1 点魔法值，使怪兽生命值减少 2，生命值变为 (-1)。

总共消耗 (3+1=4) 点魔法值即可获胜。

样例 2

输入

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

输出

100

说明

最优方案是使用第 1 种法术 100 次。

样例 3

输入

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

输出

139815