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:
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 ≤ g ≤ 10^{17}, 1 ≤ n ≤ 1000, 1 ≤ t_{i} ≤ 10^{7}, and t_{i} < s_{i} ≤ 10^{14}.
Output
For every case, print the minimum number of days needed to collect at least g gold coins.
Input
100 1 99 100 100 1 3 99 32 2 8 17 7 14 32 2 7 14 9 17 15 3 4 6 2 7 1 2 76543210987654321 1 7654321 43210987654321
Output
1 34 3 2 2 10000000130