# Conquest P57013

Statement

thehtml

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:

• Taxes: the town will pay ti gold coins every day, starting the same day it is conquered.
• Sacking: the army will get si 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 ti si. Assume 1 ≤ g ≤ 1017, 1 ≤ n ≤ 1000, 1 ≤ ti ≤ 107, and ti < si ≤ 1014.

Output

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

Public test cases
• 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
```
• Information
Author
Félix Miravé
Language
English
Official solutions
C++
User solutions
C++