题目描述

给定 $N$ 个正整数 $A_1,A_2,…,A_N$，从中选出若干个数，使它们的和为 $M$，求有多少种选择方案。

如：$N$=5,5个数分别为1,2,3,4,5，$M$=5；

那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。

输入格式

第一行包含两个整数 $N$ 和$M$。

第二行包含 $N$个整数，表示 $A_1,A_2,…,A_N$。

输出格式

包含一个整数，表示可选方案数。

答案保证在 int 范围内。

样例

4 4
1 1 2 2

3

5 5
1 2 3 4 5

3

数据范围

$1≤N≤100, 1≤M≤10000, 1≤A_i≤1000$

来源

• 一本通在线评测
• 算法竞赛进阶指南