文理学院程序设计在线练习


关键的硬币

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 26   Accepted Submission(s): 17
Problem Description

小希有一些硬币,每个硬币有着自己的面值ci,她希望对于任何一个[1,d]范围内的数字,她都可以选出一些硬币,使得这些硬币的面值和为该数字。
小希觉得如果这些硬币中扔掉一个,那么这些硬币就无法组成[1,d]范围内的所有数字了,那么这枚硬币就是关键的硬币。
小希希望你找出所有关键的硬币。
如果一开始就无法凑成[1,d]范围内的所有数字,则输出-1。

Input

第一行输入一个整数T,表示数据组数(T<=200)。
每组数据第一行输入两个整数n,d,分别代表小希现有的硬币数量和她想达成的范围为[1,d]。
随后一行,输入n个整数,分别表示第i枚硬币的面值ci。其中,
1 <= n <= 20
1 <= ci,d <= 100

Output

对于每组数据,输出一个整数,表示关键硬币的数量;如果一开始就无法凑成[1,d]范围内的所有数字,则输出-1。

Sample Input
3
3 3
1 1 3
3 2
1 1 3
3 100
1 5 80
Sample Output
3
2
-1
Hint

样例1中,如果扔掉任何一枚1,就无法凑出2,如果扔掉3,则无法凑出3,所以所有的硬币都是关键硬币,共计3枚。
样例2中,如果扔掉任何一枚1,就无法凑出2,共计2枚。
样例3中,显然一开始就无法凑足[1,100]中所有数字(比如2,3,4都凑不出来),故输出-1。

Source

2019校赛