diskete
One nice and sunny spring day in November, Gustav was at home playing on his computer. And it would be just an ordinary day if Gustav hadn't accidentaly, while playing some games, broken his computer. He was suprised and terrified. He immediately called his friend Marin to come and help him save all his programming codes, because he would be lost without them. Marin arrived soon, carying a Special Device For Saving Data From Destroyed Hard-Disks(SDFSDFDHD), together with the latest models of data storage disks called MarinUltraDisks( MUD, but it has nothing to do with mud). But, in order for disk to work properly, the whole disk's capacity must be used for storing the data.
So they decided to store all of the Gustav's codes to those disks. But a new problem appeared; Gustav had really a lot of codes so they needed really a lot of space to store the disks. And Gustav has no shelfs in his room. AAAAAAAAAAAA!!!
And here you come. It is necessary, instead of Marin and Gustav, who are not that good at maths, and even less in programming, to make a program which will calculate the minimum possible width of all the disks together so that all of the Gustav codes could be stored on them, so that Gustav could know how many shelfs does he need to buy.
In the first line of input there are 2 numbers, M and N. M is the amount of data on Gustav's broken hard-disk in MB, and N is a number of different disks which Marin and Gustav can use for storing the codes( they can use any number of disks because of Marin's special credits to the disks factory he can get unlimited amount of any disks for free ). 1 < M < 100 000, 1 < N < 50.
In each of the next N lines there will be two integers, Ci and Di, capacity and width of the i-th type of disks( 1 <= Ci <= M, 1 <= Di <= 10 000 ).
Your program should write one number, a minimal width of all used disks so that all the Gustav's codes can be saved.
Input:
100 10
1 10
2 9
3 8
4 7
5 6
6 5
7 4
8 3
9 2
10 1
Output:
10
Input:
556 5
50 3
100 6
5 3
1 5
3 2
Output:
37
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.