Unbounded Knapsack

Item i weighs weights[i] and is worth values[i]; you may take each item any number of times. The bag holds total weight at most capacity. Return the largest total value.

For weights = [1, 3, 4], values = [15, 50, 60] and capacity = 8 the answer is 130 (two items of weight 3 and two of weight 1).

Examples

Example 1

Input:

unbounded_knapsack([1, 3, 4], [15, 50, 60], 8)

Output:

130

Example 2

Input:

unbounded_knapsack([5], [10], 4)

Output:

0

Constraints

• 0 <= number of items <= 100
• 1 <= weights[i] <= 1000, 0 <= values[i] <= 1000
• 0 <= capacity <= 20000