Knapsack Treasure Hunt

A renowned treasure hunter has discovered several mysterious caves filled with gold coins. However, his bag has a limited capacity. Your task is to help him pick the best combination of caves to maximize the total gold coins he can carry without exceeding the bag's capacity.

Formally, you are given T test cases. For each test case, you are provided with an integer N representing the number of caves and an integer C representing the bag's capacity. Each cave is associated with a positive integer value representing the number of gold coins available in that cave. You have to decide which caves to visit, so that the sum of the coins from the chosen caves is maximized while not exceeding C.

This problem can be modeled as a 0/1 knapsack problem where the weight and the value of each item are the same. The recurrence relation is given by:

\(dp[c] = \max(dp[c], dp[c-w] + w)\) for each coin value \(w\) and capacity \(c\) from \(C\) down to \(w\).

inputFormat

The first line contains a single integer T representing the number of test cases.

For each test case, the first line contains two integers N and C, where N is the number of caves and C is the capacity of the bag. The second line contains N space-separated positive integers representing the number of gold coins in each cave.

outputFormat

For each test case, output a single line containing the maximum number of gold coins that can be collected without exceeding the bag's capacity.

## sample

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

10
7
5
6

</p>