## Algorithm

B. Burglar and Matches
time limit per test
0.5 second
memory limit per test
64 megabytes
input
standard input
output
standard output

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.

Input

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

Output the only number — answer to the problem.

Examples
input
Copy
`7 35 102 53 6`
output
Copy
`62`
input
Copy
`3 31 32 23 1`
output
Copy
`7`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include<bits/stdc++.h>
using namespace std;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin>>n>>m;

multimap <int, int, greater<int>> marr;
int x, y;
for(int i = 0; i <m; i++){
cin>>x>>y;
marr.insert(pair <int, int> (y, x));

}

multimap <int, int> :: iterator itr;
int count = 0, sum = 0;
for (itr = marr.begin(); itr != marr.end(); ++itr)
{
count += itr->second;
if(count >= n){
itr->second = itr->second - (count - n);
sum += itr->first * itr->second;
break;
}
sum += itr->first * itr->second;

}
cout <<sum<< endl;

}``````
Copy The Code &

Input

cmd
7 3
5 10
2 5
3 6

Output

cmd
62