1、小 W 买礼物(bday.cpp)

1、小 W 买礼物(bday.cpp)

【问题描述】
小 W 今天很高兴,因为商店给 OIer 们发购物券了。小 W 得到了一些价值不菲的 SHOP 购物券,所以他决定买 N 件礼物送给小 M。

当小 W 选好了 N 件礼物,高兴地去结账时,他突然发现 SHOP 对购物券的使用有非常奸商(天下哪有免费的购物券?)的规定:一次只允许使用一张、不找零、不与现金混用。小 W 身上根本没有现金,并且他不愿意全部放弃挑选好的礼物。这就意味着,他只能通过这些购物券结账,而且这张购物券所购买的物品的总价格,必须精确的等于这张购物券的面额。
怎么样才能顺利的买回这 N 件礼物中的部分或全部送给小 M 呢?

你的任务就是帮助小 W 确定是否存在一个购买方案。小 W 会告诉你每张购物券的面额以及所有商品的价格,对每张购物券,你只需要确定能否找到一种选礼物方案,使得选出来的礼物的价格总和正好是这张购物券的面额即可。

【输入格式】
输入文件 bday.in 中有多组数据,每组数据的第一行为两个整数 N 和 M,分别表示小 W 一共挑选了 N 件礼物以及小 W 的一张购物券的面额为 M。接下来一行有 N 个用空格隔开的正整数,第 I 个数表示第 I 个礼物的价格。
输入数据以 0 0 结束。

【输出格式】
输出文件 bday.out 包含若干行,每行一个单词“YES”或者“NO”,分别代表存在一个购买方案和不存在一个购买方案。

Sample 1

Input

10 2000                 
1000    100 200 300 400 500 700 600 900 800
10  2290                    
1000    100 200 300 400 500 700 600 900 800
0 0                         

Output

YES
NO

Limitation

1s, 64MiB for each test case.
【数据规模】
对于 30% 的输入文件,所有的 N≤20。
对于 100% 的输入文件,所有的 N≤40,并且 M 和物品的总价值不超过 2^31-1,测试组数不超过 10 组,不少于 5 组。