Ice Hockey World Championship

Time limit1sMemory limit1024 MB

Summary

Count the subsets of up to 40 ticket prices whose total is at most M.

Level: Medium6 of 10
Topics: Divide and conquer, Sorting, Binary search
Solved: No attempts yet

Problem

This year the Ice Hockey World Championship was held in the Czech Republic. Bobek has arrived in Prague and wants to watch some of the matches. He has no favourite team and no scheduling constraints, so with enough money he could watch every match. His money is a fixed amount of Czech crowns, and he can spend all of it on tickets.

Given the ticket price of each match, count the ways Bobek can choose a set of matches without exceeding his budget. Two ways are different if some match is watched in one of them and not in the other. Watching no match at all counts as one way.

Input

The first line contains the number of matches $N$ and the amount of money Bobek can spend $M$ . ( $1 \le N \le 40$ , $1 \le M \le 10^{18}$ )

The second line contains the $N$ ticket prices separated by spaces. Each price is an integer between $1$ and $10^{16}$ .

Output

Print the number of ways on one line. Because of the limit on $N$ , this value never exceeds $2^{40}$ .

Hint

When the prices are $100$ , $1500$ , $500$ , $500$ , $1000$ and the budget is $1000$ , the eight ways are:

watch no match
the match worth $100$
the first match worth $500$
the second match worth $500$
the match worth $100$ and the first match worth $500$
the match worth $100$ and the second match worth $500$
both matches worth $500$
the match worth $1000$

Examples4

Example 1
Input
```
5 1000
100 1500 500 500 1000
```
Expected output
```
8
```
Example 2
Input
```
1 1
2
```
Expected output
```
1
```

Example 3

Input

1 1000000000000000000
10000000000000000

Expected output

Example 4
Input
```
4 10
1 2 3 4
```
Expected output
```
16
```