题目描述

\(\text{Smart}\) 在打怪兽，这只怪的初始血量为 \(H\) 。

\(\text{Smart}\) 可以念 \(N\) 种咒语，第 \(i\) 种会对怪兽的血量造成 \(A_i\) 点伤害，但是会消耗 \(B_i\) 点魔法点数。每一种咒语可以念多次。

当怪兽血量 \(H \le 0\) 时，\(\text{Smart}\) 就获胜了。

请求出 \(\text{Smart}\) 在击败怪兽的情况下，所消耗的魔法点数的最小值。

格式

输入格式

第一行两个整数 \(H\) 和 \(N\)。

接下来 \(N\) 行，每行两个整数 \(A_i，B_i\)。

输出格式

输出一行包含一个整数，表示消耗的魔法点数的最小值。

样例1

样例输入1

9 3
8 3
4 2
2 1

样例输出1

4

样例2

样例输入2

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

样例输出2

100

限制

\(100\%\)的数据：\(1 ≤ H ≤ 10^4, 1 \leq N \leq 10^3,1 \leq A_i \leq 10^4,1 \leq B_i \leq 10^4\)。