Conquest P57013


Statement
 

pdf   zip

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++