4436. [CEOI 2015] 世界冰球锦标赛

【题目描述】

2015年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。

如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

【输入格式】

第一行，两个正整数 $N$ 和 $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$，表示比赛的个数和 Bobek 那家徒四壁的财产。 

第二行，$N$ 个以空格分隔的正整数，均不超过 $10^{16}$，代表每场比赛门票的价格。

【输出格式】

输出一行，表示方案的个数。由于 $N$ 十分大，注意：答案 $\le 2^{40}$。

【样例输入】

5 1000
100 1500 500 500 1000

【样例输出】

8

【样例说明】

八种方案分别是：

- 一场都不看; 

- 价格 $100$ 的比赛; 

- 第一场价格 $500$ 的比赛; 

- 第二场价格 $500$ 的比赛;

- 价格 $100$ 的比赛和第一场价格 $500$ 的比赛;

- 价格 $100$ 的比赛和第二场价格 $500$ 的比赛;

- 两场价格 $500$ 的比赛;

- 价格 $1000$ 的比赛;

【数据规模与约定】