ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Petrozavodsk Summer 2018. t.me/umnik_team Contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Knapsack

Time limit: 4.0 second
Memory limit: 256 MB
There are n types of weights. The mass of one weight of type i+1 is not less than the mass of two weights of type i. You have exactly 2 weights of each type.
Count the number of ways to select some weights with total mass equal to W. Two ways are different if for some i, the number of selected weights of type i is different.

Input

In the first line of input, there are two integers n and W: the number of types and the desired total mass (1 ≤ n ≤ 60, 0 ≤ W ≤ 4 · 1018).
In the second line of input, there are n integers ai: the masses of the weights. It is guaranteed that 1 ≤ a1, 2 · aiai+1, and an ≤ 1018.

Output

Print a single line containing the answer to the problem.

Sample

inputoutput
5 100
2 5 10 21 49
3
Problem Author: Alexey Danilyuk
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest
To submit the solution for this problem go to the Problem set: 2123. Knapsack