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.


hide comments
Himanshu Sharma: 2016-09-12 10:07:24

HELL, bug in test data take n =100 :-|

lumaere: 2016-04-05 21:18:25

The number of objects is way too low for the time limit allotted. Can finish with brute force.

Xiaomin Zhang: 2016-03-07 09:41:13

there is some case that n>20..... and the bug of the test data, just almost drives me crazy with so many wrong answer!

:.Mohib.:: 2015-06-18 06:29:34

Awsm que... should be in classical..


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)