Maximize Flower Beauty

You are given several test cases. In each test case, there are n types of flowers, where each flower type is characterized by its space requirement and beauty contribution. Alex has a limited amount of space S, and he can choose at most one flower of each type. The objective is to maximize the total beauty without exceeding the available space.

This problem is a variant of the 0/1 knapsack problem. Formally, for each test case, you are given integers \( n \) and \( S \), an array \( space[] \) of length \( n \) indicating the space required by each flower, and an array \( beauty[] \) representing the beauty contributions. You need to select a subset of flowers such that the sum of their space does not exceed \( S \) and the sum of their beauty is maximized.

Input and Output formats are described below. Use dynamic programming to implement an efficient solution.

inputFormat

The input begins with an integer \( T \) representing the number of test cases. For each test case, the first line contains two integers \( n \) and \( S \), where \( n \) is the number of flower types and \( S \) is the total available space.

If \( n > 0 \), the second line contains \( n \) space-separated integers denoting the space requirements of the flowers, and the third line contains \( n \) space-separated integers denoting their beauty contributions. If \( n = 0 \), the test case does not provide the two additional lines.

outputFormat

For each test case, output a single integer on a new line — the maximum beauty that can be achieved without exceeding the space constraint.

## sample

2
3 5
2 3 4
3 4 5
4 10
5 4 9 1
8 10 7 6

7
24

</p>