Knapsack Counting

You are given N items and one bag that can hold total weight at most C.

Each item may be chosen at most once, and choosing no items also counts as one way. Count how many subsets of the items have total weight at most C.

The first line contains N and C. N is a positive integer no greater than 30, and C is a non-negative integer no greater than 10^9.

The second line contains the weights of the N items. Each weight is a positive integer no greater than 10^9.

Print the number of ways to choose items whose total weight is at most C.