18951번 - Knapsack 다국어

문제

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.

입력

In the first line of input, there are two integers $n$ and $W$: the number of types and the desired total mass (1ドル \le n \le 60,ドル 0ドル \le W \le 4 \cdot 10^{18}$).

In the second line of input, there are $n$ integers $a_{i}$: the masses of the weights. It is guaranteed that 1ドル \le a_{1},ドル 2ドル \cdot a_{i} \le a_{i+1},ドル and $a_{n} \le 10^{18}$.

출력

Print a single line containing the answer to the problem.

제한

힌트