Exams

Time limit1sMemory limit128 MB

Summary

Count subsets of at most 36 positive exam scores whose sum is at least T, where each score can be as large as 10^13.

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

Problem

Ivan has just been accepted into university. His curriculum contains exactly $N$ exams. The exams can differ in difficulty, so different exams may award different amounts of points.

Ivan is not required to take every exam, but the points he earns matter, because they are part of his final grade. To get a good grade he needs a total of at least $T$ points. Ivan is confident in his abilities, so whenever he decides to take an exam he receives its full score.

Ivan wants to know in how many different ways he can choose which exams to take (and which to skip) so that the sum of the points he earns is at least $T$ . Two ways are considered different if the set of exams taken differs. Taking no exam earns $0$ points.

Write a program that computes this number.

Input

The first line contains two positive integers $N$ ( $N \le 36$ ) and $T$ .

The second line contains $N$ positive integers separated by single spaces, giving the points awarded by each exam. Each of these numbers is at most $10^{13}$ .

Output

Print a single integer: the number of ways Ivan can choose a set of exams so that the sum of the earned points is at least $T$ .

Examples2

Example 1
Input
```
4 6
1 2 5 4
```
Expected output
```
9
```
Example 2
Input
```
8 90
1000 2 5 79 12 3 1 3
```
Expected output
```
166
```