9238 - 【蒙青创】昀可炫菜

题面by:霹雳大裤衩(zxc)

邓老师被陨石击中脑神经后,立刻拉着好孩子昀可到了一家……餐馆,很低端的那种。

邓老师指着墙上的价目表(太低级了没有菜单),说:“随便点”。

题目描述 不过邓老师由于去治了一下脑子,口袋里只剩 M元 (M <=10000)。

餐馆虽低端,但是菜品种类不少,有 N种 (N<=100),第 i种卖 ai元 (ai<=1000)。

由于是很低端的餐馆,所以每种菜只有一份。

昀可奉行“不把钱吃光不罢休”,所以她点单一定刚好把邓老师身上所有钱花完。她想知道有多少种点菜方法。

由于昀可为了多炫点,已经饿了114514天,所以最多只能等待 1秒。

输入

第一行是两个数字,表示 NM

第二行起 N个正数 ai(可以有相同的数字,每个数字均在 1000 以内)。

输出

一个正整数,表示点菜方案数,保证答案的范围在 int 之内

样例

输入

4 4
1
1
2
2

输出

3

输入

4 3
1
1
2
2

输出

4
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题