问题描述

在圣安东尼奥，一项颇受欢迎的活动是沿着河边步道（$River Walk$）的公园里享用玛格丽塔鸡尾酒。河边步道旁的许多场所都出售玛格丽塔，从豪华酒店到$Joe$的塔可和玛格丽塔小摊。（问题不在于探究$Joe$是如何获得酒类许可证的，因为这涉及德州政治，对$ACM$竞赛题来说太难了。）各家店的玛格丽塔价格因原料的数量、质量以及环境氛围而异。你已经拨出了一笔钱来品尝不同口味的玛格丽塔。

给定每家店单杯玛格丽塔的价格（包括税费和小费）以及用于品尝玛格丽塔的预算金额，请找出你可以购买的不同最大组合的数量。每个组合最多从每家店选一杯玛格丽塔。一个有效的组合必须满足总价格不超过预算金额，并且未使用的金额（预算金额 - 总价格）必须小于任何未被选中的店的价格。（否则，你可以将该店加入组合中。）

例如，假设你有$25预算，各店的价格（整数美元）如下：

那么可能的组合（及其总价格）为：

$ABC(25)$、$ABD(24)$、$ABJ(22)$、$ACD(23)$、$ACJ(21)$、$ADJ(20)$、$AH(24)$、$BCD(24)$、$BCJ(22)$、$BDJ(21)$、$BH(25)$、$CDJ(20)$、$CH(24)$、$DH(23)$ 和 $HJ(21)$。

因此，组合的总数为$15$。

输入格式

输入的第一行是一个整数$N$（$1 \leq N \leq 1000$），表示数据集的数量。每个数据集的第一行包含两个整数$V$和$D$，分别表示商家的数量（$1 \leq V \leq 30$）和用于消费的美元金额（$1 \leq D \leq 1000$）。这两个值之间用一个或多个空格分隔。数据集的其余部分由一行或多行组成，每行包含一个或多个整数，表示每家商家的玛格丽塔价格。总共有$V$个价格值。玛格丽塔的价格至少为$1$美元。输入值的选择将确保结果可以用$32$位无符号整数表示。

输出格式

对于每个问题实例，输出一行，包含数据集编号，后跟一个空格和该问题实例的组合数量。

输入样例$1$

2
6 25
8 9 8 7 16 5
30 250
1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

输出样例$1$

1 15
2 16509438

提示

注意：对于这个问题，某些解决方法可能在商家数量上是指数级的。对于这些方法，在商家数量较多的问题实例（如第二个样例）上可能会超出时间限制。

来源

2006年大纽约地区编程竞赛