Description

To give you one  n A monetary system of denominations , Find the face value of the composition as  m How many currencies are there .

Format

Input

The first  1 Line two integers  n and m (1<n≤1000,1<m≤10,000）;

next  n That's ok , One integer per row , Represents the amount of each face value ;

Output

The number of output schemes .

Samples

input data 1

3 10
1
2
5

Output data 1

10

Limitation

1s, 1024KiB for each test case.

Answer key ：

Have to say , It's really double H2O 了

Loop through each face value , Then from the face value to the required amount, add , State transition equation ：

dp[j]=dp[j]+dp[j-a[i]];// State transition equation  

Program ：

#include <bits/stdc++.h>
using namespace std;
long long dp[10010];// Number of schemes  
int n,m,a[1010];
int main(){
	dp[0]=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)// Traverse n Denomination  
		for(int j=a[i];j<=m;j++)
			dp[j]=dp[j]+dp[j-a[i]];// State transition equation  
	cout<<dp[m];
    return 0;
}