B. Burglar and Matchestime limit per test0.5 secondmemory limit per test64 megabytesinputstandard inputoutputstandard outputA 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.InputThe 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.OutputOutput the only number — answer to the problem.ExamplesInput7 35 102 53 6Output62Input3 31 32 23 1Output7
Input7 35 102 53 6
Output62
['greedy', 'implementation', 'sortings', '*900']