Knapsack Problem Statement

There is a potter with a limited amount of pottery clay (denoted as 'K' units) who can make 'N' different items. Each item requires a specific amount of clay and yields a certain profit. The goal is to maximize the total profit by choosing which items to make.

Input:

The first input line contains an integer ‘T’ representing the number of test cases.
For each test case:
- The first line contains two space-separated integers, ‘N’ (number of items) and ‘K’ (units of clay available).
- The second line contains ‘N’ integers, each representing the clay requirement for the corresponding item.
- The third line contains ‘N’ integers, each representing the profit obtainable from selling the corresponding item.

Output:

For each test case, output a single integer on a new line representing the maximum profit the potter can achieve.

Example:

Input:

2
3 50
10 20 30
60 100 120
2 10
5 3
20 30

Output:

220
50

Constraints:

• 1 <= T <= 100
• 1 <= N <= 100
• 1 <= K <= 100
• 1 <= profit[i] <= 10000
• 1 <= Clay[i] <= 2000
• Time Limit: 1 second

Note:

Implement the function; printing has already been handled.