🐇🐱🪙 兔猫信奥学院的魔法金币组合
☆:.｡.🐇🐱🐇🐱.｡.:☆

题目描述

在兔猫信奥学院，今天🧙加菲老师给小兔和小猫布置了一个有趣的魔法挑战：
学院图书馆里有许多【魔法金币】（不同面额）。每当施展某个魔法，都会消耗一定面额的金币。现在，给定若干种金币面额和一个魔法总价值 $amount$，请问有多少种不同的组合方式能够恰好凑成这个魔法价值？

• 每种面额的魔法金币数量无限。
• 两种组合只要对应面额的使用次数有任何不同，就被视为不同的组合。
• 如果无法凑出恰好价值 $amount$，则答案为 $0$。

输入格式

第一行：两个整数 $n\;amount$
第二行：$n$ 个互不相同的正整数，分别表示每种魔法金币的面额 $coins_i$

• $1 \le n \le 300$
• $0 \le amount \le 5000$
• $1 \le coins_i \le 5000$

输出格式

一个整数，表示凑成目标魔法价值的不同组合数

3 5
1 2 5

4

样例解释1

1. $5 = 5$
2. $5 = 2 + 2 + 1$
3. $5 = 2 + 1 + 1 + 1$
4. $5 = 1 + 1 + 1 + 1 + 1$

1 3
2

0

样例解释2

只有面额为 $2$ 的金币，无法凑出总价值 $3$，故组合数为 $0$。