时间限制: 1s内存限制: 128M

[题目描述]

小A在和一只怪物战斗, 怪物的体力是H。 小A可以使用N种魔法，使用一次第i种魔法可以减少怪物a[i]点体力, 需要消耗b[i]点魔法值。魔法的使用次数没有任何限制。 通过使用魔法，让怪物体力减少到小于等于0点，小A最少需要消耗多少魔法值?

[输入格式]

第1行，2个正整数H,N 接下来N行，每行两个正整数a[i], b[i];

[输出格式]

输出一个整数，需要的最少魔法值。

[输入输出样例]

输入

9 3

8 3

4 2

2 1

输出

4

[数据范围]

1 <= H <= 1e4; 1 <= N <= 1e3; 1 <= a[i],b[i] <= 1e4;