← 返回题目列表

AtCoder · k4pc_e

E. 第一次动态规划(简易动态规划)

中文机器翻译题面 查看原题

一定要使用动态规划

問題文

超市生鲜区 N 黄瓜的书正在销售。在收银台付款时,请检查您在生鲜区购买的黄瓜的总重量。 W 如果您购买以下产品,您将收到制作人三上的亲笔签名。

健介君很喜欢三上同学做的黄瓜,所以他想要尽可能多的签名。健介君请列出获得三上先生签名的方法。 有

課題

N 件行李,每件行李的重量均为正整数。 附上 a_i (1 ≦ i ≦ N)。

权重之和为 W 求行李件数,满足以下条件。


制約

  • 1 ≦ N ≦ 1000.
  • 1 ≦ W ≦ 1000.
  • 1 ≦ a_i ≦ 1000.

入力

N W
a_1
a_2
…
a_N

出力

问题的解决办法 在 1 行输出。


入力例 1

4 4
1
1
2
3

出力例 1

11

\{\},\ \{a_1\},\ \{a_2\},\ \{a_3\},\ \{a_4\},\ \{a_1,\ a_2\},\ \{a_1,\ a_3\},\ \{a_2,\ a_3\},\ \{a_1,\ a_4\},\ \{a_2,\ a_4\},\ \{a_1,\ a_2,\ a_3\} 是满足条件的包的集合。