0-1 Knapsack Problem

A thief is planning to rob a store and has a knapsack that can carry a maximal weight of W. There are N items available, where each item i has a weight wi and a value vi. Determine the maximum total value of items the thief can carry without exceeding the weight limit of the knapsack.

Input:

The first line contains a single integer T, representing the number of test cases. 
For each test case, the input consists of: 

  

   
An integer N, denoting the number of items.
 
   
N space-separated integers representing the weights of the items.
 
   
N space-separated integers representing the values of the items.
 
   
An integer W, denoting the maximum capacity of the knapsack.
  

Output:

For each test case, output a single integer representing the maximum value that can be attained without exceeding the knapsack's weight capacity. Each result should be printed on a new line.

Example:

Input:

1
4
2 3 4 5
3 4 5 6
5

Output:

7

Explanation:

In the given test case, the thief can carry items with weight 2 and 3 for a total value of 3 + 4 = 7, which is the maximum possible value without exceeding the capacity W=5.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^2
• 1 <= wi <= 50
• 1 <= vi <= 10^2
• 1 <= W <= 10^3
• Time Limit: 1 second

Note:

Can this problem be solved with a space complexity of no more than O(W)?