Background

Gauss has a dragon, which does all kinds of evil and plunders "Peiyou" everywhere, bringing great pain to the people. Since the elf level reached Lv.2, they decided to exterminate the evil dragon and defeat it.

高斯拥有一条恶龙，这条龙平时无恶不作，到处掠夺《培优》，给人民带来了极大的痛苦，自从小精灵的等级达到Lv.2后，他们决定去为民除害，击败这条恶龙。

Description

It is known that the blood volume of this dragon is h. Elves can use n skills. skill I deals Ai damage to dragon, but consumes Bi magic points. Each skill can be used many times. When the dragon's health H≤0, it wins. Due to the limited number of magic points, the minimum number of magic points consumed when the elf is requested to defeat the dragon.

已知这条恶龙的血量为 H 。小精灵可以使用N 种技能，第 i种技能会对恶龙造成 Ai点伤害，但是会消耗 Bi点魔法点数。每一种技能以使用多次。当恶龙血量H≤0 时，就获胜了。
由于魔法点数有限，所以请求出小精灵击败恶龙的情况下，所消耗的魔法点数的最小值。

Input

The first row contains two integers h and n, representing the dragon's blood volume and n skills.
The next n lines, each with two integers Ai and Bi, respectively represent Ai damage to dragon caused by skill I and Bi magic points consumed by skill I.

第一行两个整数H和N，表示恶龙的血量和N种技能。
接下来N行，每行两个整数Ai和Bi，分别表示第 i种技能会对恶龙造成 Ai点伤害，和使用第i种技能消耗 的Bi点魔法点数。

Output

Print the minimum total Magic Points that have to be consumed before winning.
输出获胜前必须消耗的最小总魔法点数。

Input

9 3
8 3
4 2
2 1

Output

4

Limitation

1<=H<=104
1<=N<=103
1<=Ai<=104
1<=Bi<=104
所有输入均为整数！
时间限制：2ms

Source

Amorphophallus Orz Group