A7755 | Burglar and Matches

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 $a_{i}$ matchboxes, and each matchbox contains $b_{i}$ 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·10^{8}$ ) and integer $m$ ( $1<=m<=20$ ). The $i+1$ -th line contains a pair of numbers $a_{i}$ and $b_{i}$ ( $1<=a_{i}<=10^{8},1<=b_{i}<=10$ ). All the input numbers are integer.

Output the only number — answer to the problem.