A Order

Problem Statement

不过 uim 由于买了一些书，口袋里只剩 $M$ 元 $(M \le 10000)$。

餐馆虽低端，但是菜品种类不少，有 $N$ 种 $(N \le 100)$，第 $i$ 种卖 $a_i$ 元 $(a_i \le 1000)$。由于是很低端的餐馆，所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿，所以最多只能等待 $1$ 秒。

Input

第一行是两个数字，表示 $N$ 和 $M$。

第二行起 $N$ 个正数 $a_i$（可以有相同的数字，每个数字均在 $1000$ 以内）。

Output

一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

Sample Input

Sample Output

1

3

Solving

 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


void solve()
{
    int n,m;
    cin >> n >> m;
    int arr[n+1];
    int dp[m+1];//dp[i]表示当uim有i元时，刚好花完所有钱的点菜方法
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++) cin >> arr[i];
    dp[0] = 1;//只有零元钱时只有一种点菜方法：什么都不点
    for(int i=1;i<=n;i++)
    {   
        //case 1：钱够，选择买和不买
        for(int j=m;j>=arr[i];j--)
        {   
            //总的方法数就是，买和不买的方法数的总和
            dp[j] = dp[j] + dp[j-arr[i]];
        }
        // case 2：钱不够只能不买
        // 只是为方便理解，程序中可以不写
        // for(int j=arr[i]-1;j>0;j--)
        // {
        //     dp[j] = dp[j];
        // }
    }
    cout << dp[m];
}