#P18235. Items

Items

Items

Ivan 有 nn 种物品,每种物品都有无限多个。第 ii 种物品的重量为 wiw_i。

他想知道,能否恰好选出 nn 件物品,使它们的总重量恰好为 mm。

可以多次选择同一种物品,也可以完全不选择某种物品;不同种类的物品重量可能相同,重量也可能为 00。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含两行:

  • 第一行两个整数 n,mn,m。
  • 第二行 nn 个整数 w1,w2,…,wnw_1,w_2,\ldots,w_n。

数据范围:

  • 1≤T≤1041\le T\le10^4;
  • 1≤n≤1051\le n\le10^5;
  • 0≤m≤n20\le m\le n^2;
  • 0≤wi≤n0\le w_i\le n;
  • 同一输入文件所有测试用例的 nn 之和不超过 10510^5。

输出格式

每个测试用例输出一行。若存在符合要求的选择,输出 Yes,否则输出 No。

输出不区分大小写,例如 yEs、yes、Yes、YES 均表示肯定回答。

样例

4
5 25
0 0 0 0 5
5 11
4 4 4 5 5
5 0
1 2 3 4 5
5 25
0 1 2 3 4
Yes
No
No
No

第一个测试用例可以选择第 55 种物品的 55 件,总重量为 2525。

第二个测试用例不存在符合要求的选择。

第三个测试用例必须选取 55 件物品,最轻的物品重量为 11,因此总重量不可能为 00。

第四个测试用例最重的物品重量为 44,选取 55 件后的总重量不可能达到 2525。