0-1 Knapsack Problem Statement

A thief plans to rob a store and can carry a maximum weight 'W' in his knapsack. There are 'N' items, with the i-th item weighing wi and having a value vi. Determine the maximum value the thief can obtain while respecting the knapsack's weight limit.

Input:

 The input begins with an integer 'T', representing the number of test cases. 

 For each test case, the format is as follows: 

 An integer 'N', the number of items. 

 N space-separated integers indicating the weights of the items. 

 N space-separated integers indicating the values of the items. 

 An integer 'W', the maximum weight the knapsack can carry. 

Output:

 For each test case, output a single line containing the maximum value achievable with the given constraints. 

Example:

Input:

 2 
 3 
 1 2 3 
 10 15 40 
 6 
 2 
 1 2 
 10 20 
 2 

Output:

 55 
 20 

The first test case shows the optimal value from weights [1, 2, 3] with values [10, 15, 40] when weight is restricted to 6, the maximum value is 55. The second case shows that only one item with value 20 can be taken.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10²
• 1 ≤ wi ≤ 50
• 1 ≤ vi ≤ 10²
• 1 ≤ W ≤ 10³

Time Limit: 1 second

Note:

You are not required to print anything; the function will return the answer.