Maximum Profit Knapsack Problem

In this problem, you are given multiple projects, each of which requires a certain budget and yields a certain profit. You must determine the maximum total profit that can be achieved without exceeding the given budget for each test case. This is a variant of the classic 0/1 knapsack problem.

For each test case, you are given an integer (N) representing the number of projects and an integer (B) representing the total available budget. Then, two lists of (N) integers are provided: the first list contains the required budgets for the projects, and the second list contains the expected profits.

The solution is based on dynamic programming using the recurrence:
(dp[i][w] = \max{profit_{i-1} + dp[i-1][w-cost_{i-1}],\ dp[i-1][w]}) if (cost_{i-1} \leq w), otherwise (dp[i][w] = dp[i-1][w]).

inputFormat

The input begins with an integer (T) indicating the number of test cases. For each test case, the input is as follows:
1. A line containing two integers (N) and (B), where (N) is the number of projects and (B) is the total available budget.
2. A line containing (N) space-separated integers representing the required budgets for each project.
3. A line containing (N) space-separated integers representing the expected profits from each project.

outputFormat

For each test case, output a single integer on a new line representing the maximum profit achievable without exceeding the budget.## sample

2
3 50
20 30 40
30 40 50
4 60
10 20 30 40
40 30 20 50

70
90