Packing for a Trip

You are preparing for a hiking trip. You have a backpack with a weight limit (capacity) and a list of items, each with a weight and a utility score (value). Your goal is to pack the most useful items into the backpack without exceeding its weight limit.

Input

• An array values where values[i] represents the utility score of the i-th item.
• An array weights where weights[i] represents the weight of the i-th item.
• An integer capacity representing the maximum weight the backpack can hold.

Output

• Return the maximum utility score you can achieve by packing items without exceeding the weight limit.

Constraints

• 1 <= values.length, weights.length <= 100
• values.length == weights.length
• 1 <= weights[i], values[i] <= 1000
• 1 <= capacity <= 10^4

Example

Input

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

Output

220

Explanation

• You can select the items with utility scores of 100 and 120, with respective weights 20 and 30. The total weight is 50, and the total utility score is 220.

Notes

• This is a variation of the 0/1 Knapsack Problem.
• Each item can be included at most once.
• Use dynamic programming to optimize the solution.

Output will appear here…