题目描述

小明正在进行严格的饮食管理，今天的摄入热量不能超过 $k$ 大卡。现在面前有 $n$ 种独立包装的零食，第 $i$ 种零食含有 $c_i$ 大卡热量。每种零食小明最多选择吃一次，也可以一种都不吃。

请问，有多少种选择零食的方案（包括什么都不吃），使得摄入的总热量不超过 $k$？

输入格式

第一行两个整数 $n$ 和 $k$。

接下来 $n$ 行，每行一个整数 $c_i$，表示该零食的热量。

输出格式

一个整数，表示方案数。

样例

3 5
2 3 5

5

4 10
2 3 4 5

13

样例1解释

总热量 $≤5$ 的子集有：$\{\ \}(0)$，$\{2\}$，$\{3\}$，$\{5\}$，$\{2,\ 3\}$ 共 $5$ 种。

数据范围

对于 $30\%$ 的数据，$1\le n\le 20$。

对于 $100\%$ 的数据，$1 \le n \le 50$，$1 \le c_i \le 100$，$1\le k\le 5000$。