Pack the Knapsack

You are packing a bag that holds at most capacity kilograms. Item i weighs weights[i] kilograms and is worth values[i]. There is one of each item, and each is either packed whole or left behind.

Write best_value(weights, values, capacity) that returns the largest total value you can fit in the bag.

Examples

best_value([4, 2, 3, 6], [20, 9, 13, 27], 9)  # returns 42
best_value([6, 5, 5], [30, 20, 20], 10)       # returns 40
best_value([10], [100], 5)                    # returns 0

In the second example the first item is worth the most per kilogram, yet the best plan leaves it out: the two 5 kg items fill the bag exactly and are worth 40 together.

Constraints

• 0 <= len(weights) == len(values) <= 100
• 1 <= weights[i] <= 1000
• 0 <= values[i] <= 10**6
• 0 <= capacity <= 1000