2074 - 货币问题

题目描述

某国家有 n 种不同面值的货币,第 i 种货币价值 a_i 元。

请问:如果每种货币都提供任意多的数量的情况下,如果需要 m 元金额的货币,有多少种不同的方案?

输入

第一行两个整数 nmm \le 5000,n \le 100);

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

输出

一个整数,为方案数(方案数 \le 1018)。

样例

输入

3 10
1
2
5

输出

10
来源

动态规划 背包

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 483
通过人数 284
金币数量 1 枚
难度 入门


上一题 下一题