5555: 01背包方案总数 —— 小周周点菜
[Creator : ]
Description
今天小周周由于表现很好,获得了 $M\ (M \leq 10000)$ 的奖励。他决定请同学到饭店吃顿大餐。
饭店有 $N\ (N \le 100)$种菜,第 $i$ 种卖 $a_i\ (a_i \le 1000)$ 元。本着节约的原则,以每种菜只能点一份。
小周周奉行“不把钱吃光不罢休”,所以他点单一定刚好吧身上所有钱花完。他想知道有多少种点菜方法。
饭店有 $N\ (N \le 100)$种菜,第 $i$ 种卖 $a_i\ (a_i \le 1000)$ 元。本着节约的原则,以每种菜只能点一份。
小周周奉行“不把钱吃光不罢休”,所以他点单一定刚好吧身上所有钱花完。他想知道有多少种点菜方法。
Input
第一行是两个数字,表示 $N$ 和 $M$。
第二行起 $N$ 个正数 $a_i$(可以有相同的数字,每个数字均在 $1000$ 以内)。
第二行起 $N$ 个正数 $a_i$(可以有相同的数字,每个数字均在 $1000$ 以内)。
Output
一个正整数,表示点菜方案数,保证答案的范围在 int 之内。
Sample 1 Input
4 4
1 1 2 2
Sample 1 Output
3