0/1 Knapsack

Item i weighs weights[i] and is worth values[i]. The bag holds total weight at most capacity. Use each item at most once. Return the largest total value.

For weights = [1, 3, 4, 5], values = [1, 4, 5, 7] and capacity = 7 the answer is 9 (items of weight 3 and 4).

Examples

Example 1

Input:

knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)

Output:

9

Example 2

Input:

knapsack([10], [100], 5)

Output:

0

Constraints

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