knapsack-1

Problem Statement

Given a list of n integers, A={a1,a2,…,an}, and another integer, k representing the expected sum. Select zero or more numbers from A such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum (k).

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 comprises of two lines. First line contains two integers, n k, representing the length of list A and expected sum, respectively. Second line consists of n space separated integers, a1,a2,…,an, representing the elements of list A.

Constraints
1≤T≤10
1≤n≤2000
1≤k≤2000
1≤ai≤2000,where i∈[1,n]

Output Format

Output T lines, the answer for each test case.

SAMPLE INPUT
3
1 6
5
6 8
3 3 3 3 3 3
9 10
9 4 4 9 4 9 9 9 9

SAMPLE OUTPUT
5
6
9

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: