2838 - 货币系统

题目描述

A 国的货币系统有 N 种各类面额的货币;

现要构建总面额为 V ,各类面额的货币可以任意选用,请问有多少种不同的方法来构建该面额的货币。

比如:有 1 2 5 三种面额的货币各若干张,要构建总面额为 18 的货币,可以选择:18 张面额为 1 元的货币,或者选择 9 张面额为 2 元的货币,或者选择 3 张面额为 5 元的货币 + 1 张面额为 2 元的货币 + 1 张面额为 1 元的货币,等方案。

输入

1 行读入 2 个整数 NV。(1 \le N \le 251 \le V \le 10000

2 行有空格隔开的 N 个整数,代表货币系统可以提供的货币面额。

输出

输出一个整数,代表可以构建出总额为 V 的货币组成的方案数。(方案数在 64 位有符号整数的范围内)

样例

输入

3 10
1 2 5

输出

10
来源

东方博宜OJ

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


上一题 下一题