A vending-machine restocker is filling a shelf of capacity W. There are n item types; type i has weight w_i and value v_i, and an UNLIMITED supply is available (any non-negative number of units of each type may be placed on the shelf). Choose how many units of each type to place so total weight does not exceed W, maximizing total value.
Line 1: two integers n W.
Line 2: n space-separated integers, the item weights (empty if n = 0).
Line 3: n space-separated integers, the item values (empty if n = 0).
A single integer: the maximum total value achievable within capacity W.
Example 1
Input
2 8 3 4 4 5
Expected
10
Explanation
Taking two units of the weight-4 item uses all 8 capacity for value 10, better than any mix with the weight-3 item.
Example 2
Input
1 5 10 100
Expected
0
Explanation
The only item weighs 10, more than the capacity of 5, so none can be placed: answer 0.
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 →