题目描述

某国家有 $n$ 种不同面值的货币，第 $i$ 种货币价值 $a_i$ 元。请问：如果每种货币都提供任意多的数量的情况下，凑出 $m$ 元金额的货币，有多少种不同的方案？

注意：方案不考虑顺序，例如 $1+2$ 和 $2+1$ 视为同一种方案。

输入格式

第一行：两个整数 $n,m$；

以下 $n$ 行：每行一个整数，第 $i+1$ 行为第 $i$ 种货币的面值 $a_i$。

输出格式

仅一行，一个整数，表示不同的方案数。

样例

3 10
1
2
5

10

提示

样例解释

凑出 $10$ 元的 $10$ 种方案如下：

1. $1+1+1+1+1+1+1+1+1+1$
2. $1+1+1+1+1+1+1+1+2$
3. $1+1+1+1+1+1+2+2$
4. $1+1+1+1+2+2+2$
5. $1+1+2+2+2+2$
6. $2+2+2+2+2$
7. $1+1+1+1+1+5$
8. $1+1+1+2+5$
9. $1+2+2+5$
10. $5+5$

数据范围

$1\le n\le 100$

$1\le m\le 5000$

$1\le a_i\le m$

方案数 $\le 10^{18}$

来源

动态规划 完全背包