Sandun is a wine lover. He had to be in his home for three months due to the Covid-19 situation. Sandun wants to buy some wine since the curfew has been lifted. He goes to his favorite wine yard with some empty bottles. Wine yard owner is pleased to see Sandun. Hence, he offers Sandun free wine on one condition. Sandun can fill only the bottles he carries in his bag.
Wine barrels in the wine yard have a tag in each one of them which has two values containing the number of bottles in the barrel and the price of the whole barrel.
You have to build a program to help Sandun to take maximum valued wine from this offer. Given the number of bottles that he brought and the information on the wine barrels, you have to find the maximum value of wines Sandun gets from this deal.
Please note that he cannot fill any of the bottles with more than one type of wine. Assume that the bottle is a 750ml glass bottle. Input Format
->First Line contains two integers N and M. N is the number of bottles Sandun brought and M is the number of barrels in the wine yard. ->Second-line contains M space-separated integers contain the volume of barrels in bottles. ->The third line contains the M space-separated integers containing the price of each barrel.
Output Format ->One integer containing the maximum value of wines Sandun gets from the offer.
Example : Input: 5 3 1 2 3 6 10 12
Output : 24
Explanation ->He can fill one bottle from 1st barrel, two bottles from 2nd barrel and another 2 bottles from third barrel which gives maximum value of 24