Conquest P57013

0.52

It is summer in the land of Max-Flow and Lord Push-Relabel wants to build a swimming pool in the yard next to his castle, which will cost $g$ gold coins. So he is sending his invincible army to conquer some of the $n$ nearby towns. His soldiers can conquer one town per day, and afterwards they will use one of the following methods to acquire gold from it:

0.48

• Taxes: the town will pay $t_i$ gold coins every day, starting the same day it is conquered.

• Sacking: the army will get $s_i$ gold coins by looting the town the very same day it is conquered, but this will leave the town unable to pay taxes in the future.

Lord Push-Relabel wants to minimize the number of days to acquire the desired amount of gold $g$. Please plan which towns to conquer, in what order, and for each conquered town whether it should be taxed or sacked.

Input

Input consists of several cases. Every case begins with $g$ and $n$, followed $n$ pairs $t_i$ $s_i$. Assume $1 \le g \le 10^{17}$, $1 \le n \le 1000$, $1 \le t_i \le 10^7$, and $t_i < s_i \le 10^{14}$.

Output

For every case, print the minimum number of days needed to collect at least $g$ gold coins.