10958번 - Ice Hockey World Championship 다국어

This year the Ice Hockey World Championship took place in the Czech Republic. Bobek has arrived in Prague and he would like to visit some of the matches. He does not have any team preferences and he does not have any time restrictions. If he had enough money, he would be able to visit all of the matches. Unfortunately, he has only a limited number of Czech crowns, all of which can be spent on tickets. Knowing how much a ticket costs for each match, calculate the number of ways he can attend a set of matches without exceeding his budget. Two ways are considered different if there exists a match which is visited in one of the ways, but not visited in the other.

A description of Bobek’s situation is read from the standard input. The first line of input contains two positive integers N and M (1 ≤ N ≤ 40, 1 ≤ M ≤ 10¹⁸), denoting the number of matches and the number of Czech crowns Bobek can spend. The second line contains N space-separated positive integers, none of them exceeding 10¹⁶, representing costs of the matches in Czech crowns.

Output a single line with the number of ways Bobek can visit the matches. Please note that due to the limit on N, this number will be at most 2⁴⁰.

The eight possible ways are:

• no matches visited
• 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.