Algorithm
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
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;
}Input
5 10
2 5
3 6
Output
Demonstration
Codeforcess Solution 16-B B. Burglar and Matches ,C++, Java, Js and Python,16-B,Codeforcess Solution