凑钱

Time Limit:1000MS Memory Limit:65536K
Total Submit:1 Accepted:0

Description

某国的货币只有n种，它们的面值分别是value1,value2,...,valuen.现在我要买一件商品，它值cost元.我只能用这n种货币付款,并且每种货币我有任意枚。n种货币凑齐cost元吗？如果能够凑齐的话，最少需要多少枚货币呢？

Input

每组测试数据占2行。
第一行有2个正整数n，cost(0＜n＜1000，0＜cost＜=10000)。
第二行有n个整数，表示value1,value2,...,valuen(0＜valuei＜=10000)。

Output

每组测试数据输出它的结果，占一行。如果能够凑好，输出需要最少的货币数;否则输入"bad".

Sample Input

4 10
1 2 5 10
4 13
2 4 6 8

Sample Output

1
bad

[此贴子已经被作者于2007-11-2 16:00:12编辑过]

我昨天也是这样排序 然后挑大的 但是 比如
对于输入的
1 2 5 10
13元 结果 3
17元 结果 3