Problem Description

Translated from CEOI2015 Day2 T1 “Ice Hockey World Championship”.

This year’s Ice Hockey World Championship is held in the Czech Republic. Bobek has arrived in Prague. He is not a fan of any team, and he has no sense of time. He simply wants to watch some matches. If he had enough money, he would watch all the matches. Unfortunately, his money is very limited, so he decides to spend all his money on tickets.

Given Bobek’s budget and the ticket price of each match, find: how many different ways he can choose matches to watch such that the total ticket cost does not exceed the budget. If there exists a match that is watched in one plan but not watched in another plan, then the two plans are considered different.

Input Format

The first line contains two positive integers $N$ and $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$, denoting the number of matches and Bobek’s extremely limited budget.

The second line contains $N$ positive integers separated by spaces, each not exceeding $10^{16}$, representing the ticket price of each match.

Output Format

Output one line containing the number of plans. Since $N$ is very large, note that the answer $\le 2^{40}$.

5 1000
100 1500 500 500 1000

8

Hint

Sample Explanation

The eight plans are:

• Watch no matches and leave.
• The match with price $100$.
• The first match with price $500$.
• The second match with price $500$.
• The match with price $100$ and the first match with price $500$.
• The match with price $100$ and the second match with price $500$.
• Both matches with price $500$.
• The match with price $1000$.

There are 10 test groups. For each group you pass, you get 10 points. The Constraints for each group are shown in the table below:

Translated by ChatGPT 5