Description
The description provided for this problem:
Once Agent Ω was able to isolate a collection of smart bricks, her tech team were able to reverse engineer them and build more of their own. The main limitation they had were total power consumption. Each power source funnels into a chain of bricks and each brick consumes power proportional to its speed. This means that when Agent Ω puts a chain together, she has a maximum amount of total speed that the power source can handle. If she tries to build an AI that goes too fast, the power source will burn out.
There are N types of smart bricks the engineers now know how to make. Each Brick i has speed Bi with K being the maximum total speed before the power source burns out. Determine that maximum total speed that can be constructed in practice the the brick types that Agent Ω has access to.
For example, if there were types of bricks that had a speed of 9 and 12 respectively, and the power source could handle a maximum total speed of 31, you would be able to produce a maximum of 30 units by pressing two of the first brick type and one of the second brick type. If there were also a brick type of speed 1, you would be able to maximize the heat to a perfect 31, but no such brick type exists so no existing combination of bricks can get you all the way to 31.
Input Format
The first line contains T, the number of test cases.
Each test comprises two lines:
The first line contains two integers, N and K, representing the number of brick types and maximum power available, respectively.
The second line consists of space separated integers, B0 through BN-1, representing the speed of each brick type.
Constraints
1 ≤ T ≤ 10
1 ≤ N, K ≤ 2000
1 ≤ Bi ≤ 2000
Output Format
Output T lines, the maximum total speed can be produced in each test case without exceeding the total speed limit ( K ).
Example 0
Sample Input
3
3 12
1 6 9
5 9
3 4 4 4 8
4 11
5 7 8 9
Sample Output
12
9
10
Explanation
In the first test case, you can use two of the speed-6 bricks to achieve the maximum total speed of 12.
In the second test case, you can use three of the speed-3 bricks to hit the maximum total speed of 9.
In the third test case, there is no way to reach the speed limit of 11, so the closest you can come is 10, by using two of the speed-5 bricks.
Example 1
input01.txt
output01.txt
Example 2
input02.txt
output02.txt
Example 3
input05.txt
output05.txt
Example 4
input06.txt
output06.txt
Example 5
Sample Input
1
8 10
11 12 13 14 15 16 17 3
Sample Output
9
Explanation
The first seven brick types are useless since they immediately exceed the limit. The best we can do is use three of the last type for a total of 9.
