Ice Hockey World Championship

This problem is adapted from CEOI 2015 Day2 T1 Ice Hockey World Championship.

Bobek has arrived in Prague for the world ice hockey championship. He is not a fan of any particular team and has no time constraints – he just wants to catch as many games as possible. However, his funds are extremely limited; he has decided to spend his entire budget on tickets. Given his budget and the ticket prices for each match, determine the number of distinct match-watching schemes such that the total ticket price does not exceed his budget. Two schemes are considered different if there exists a match that is watched in one scheme and not watched in the other.

The problem can be formulated mathematically as follows. Let \(p_1, p_2, \dots, p_n\) be the ticket prices for the \(n\) matches and let \(m\) denote Bobek's budget. We wish to count the number of subsets \(S \subseteq \{1, 2, \dots, n\}\) such that

[ \sum_{i \in S} p_i \le m. ]

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) is the number of matches and \(m\) is Bobek's budget.

The second line contains \(n\) integers \(p_1, p_2, \dots, p_n\) representing the ticket price for each match.

outputFormat

Output a single integer: the number of different ways Bobek can choose a set of matches to attend such that the total ticket price does not exceed \(m\).

sample

3 6
1 2 3

8