Problem Statement

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W.

Examples

Example 1

Input: values = [60, 100, 120], weights = [10, 20, 30], W = 50
Output: 220
Explanation: Pick item 2 and item 3 for weights 20 + 30 = 50, value 100 + 120 = 220.

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ weights[i], values[i] ≤ 1000
• 1 ≤ W ≤ 1000