题目描述

给定$n$个数$a_i$，要求选择一些数，可以不选，并且这些数的和不超过$m$，问选数的方案有多少种。

输入格式

第一行输入两个整数$n,m$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

5 1000
100 1500 500 500 1000

样例输出 #1

8

说明/提示

有$1\leq n\leq 40,1\leq m\leq 10^{18},1\leq a_i\leq 10^{16}$。