A burglar got into a matches warehouse and wants to steal as many matches as possible. In the warehouse there are m containers, in the i-th container there are ai matchboxes, and each matchbox contains bi matches. All the matchboxes are of the same size. The burglar's rucksack can hold n matchboxes exactly. Your task is to find out the maximum amount of matches that a burglar can carry away. He has no time to rearrange matches in the matchboxes, that's why he just chooses not more than n matchboxes so that the total amount of matches in them is maximal.
The first line of the input contains integer n (1≤n≤2·108) and integer m (1≤m≤20). The i+1-th line contains a pair of numbers ai and bi (1≤ai≤108,1≤bi≤10). All the input numbers are integer.
Output the only number − answer to the problem.
7 3
5 10
2 5
3 6
62
3 3
1 3
2 2
3 1
7