Once Algorithm guru gave a simple problem to his students.He gave a list of n integers say, A={a1,a2,a3...an} and another integer, x representing the expected sum. He said students to select numbers from array list(0 or more numbers) such that the sum of these numbers is as close as possible but not exceeding to the sum x.
Note:Each element of A can be selected multiple times.If no element is selected then the sum is 0.
Input Format:
The first line contains T the number of test cases. Each test case is followed by two lines. First line contains two integers n,x, representing the length of list A and expected sum. Second line consists of n space separated integers, a1,a2,…,an, representing the elements of list A.
Output Format:
Output T lines, the maximum sum for each test case which is as near as possible, but not exceeding, to the expected sum x.
Constraints:
1≤T≤10
1≤n≤3000
1≤x≤3000
1≤ai≤3000,(1<=i<=n)
In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}
