CODEM5 - Problem5

You are given an array of weights of n objects and your task is to select minimum number of objects whose sum of weights is exactly equals to some given k.

Input

Line 1 - number of test cases T (<= 10) followed by 2 lines for each test case
Line 2 - Number of objects n (<= 20) and total weight k (<= 10^4)
Line 3 - weights (<= 10^4) of n objects (each separated by space)

Output

Minimum number of objects whose weights sums to k.

Example

Input:
2
5 9
10 9 4 3 5
3 7
1 2 3 Output: 1
impossible

Explanation

For the first case the two combinations are possible: (9), (4, 5) hence minimum number of objects is 1.

For the second case there are no combinations possible hence impossible.


Added by:Bhavik
Date:2014-02-04
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem(for CODE MARATHON)

hide comments
2016-09-12 10:07:24 Himanshu Sharma
HELL, bug in test data take n =100 :-|
2016-04-05 21:18:25
The number of objects is way too low for the time limit allotted. Can finish with brute force.
2016-03-07 09:41:13 Xiaomin Zhang
there is some case that n>20..... and the bug of the test data, just almost drives me crazy with so many wrong answer!
2015-06-18 06:29:34 :.Mohib.:
Awsm que... should be in classical..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.