A vending hopper has a fixed volume of C units. There are n product types; type i occupies w_i units of volume and yields v_i profit per unit stocked. You have an unlimited supply of every type and may stock any type any number of times (including zero). Choose quantities so the total volume used is at most C and the total profit is maximized. Report that maximum profit (0 if nothing fits).
Line 1: two integers n and C.
Next n lines: two integers w_i and v_i for each product type.
A single integer: the maximum total profit for total volume at most C.
Example 1
Input
2 5 2 3 3 5
Expected
8
Explanation
Stocking one of each type uses volume 2 + 3 = 5 for profit 3 + 5 = 8, the best possible within volume 5.
Example 2
Input
1 7 3 4
Expected
8
Explanation
Two copies of the only type use volume 6 (within 7) for profit 8; a third copy would need volume 9 and does not fit.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →