You are given factories and total number of boxes which you must fulfill. Each factory has 2 values, and , denoting the price in cents that factory charges for one box, and the total number of boxes factory has respectively.
Please find the minimum price in cents in order to obtain at least boxes. It is guaranteed that at least boxes can be achieved.
First line contains 2 integers, and .
Next lines each contain 2 integers, and .
Output the minimum price in cents in order to obtain at least boxes.
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
5 100 5 20 9 40 3 10 8 80 6 30
|Price per Box||Units available||Units bought||Prices # of units||Total Cost||Notes|
|Bought no boxes from factory 2|
|Did not buy all 80 units|
|Total||Cheapest total cost|