The boolean satisfiability problem is a famous problem in computer science. You are given booleans, and a list of numbers. A boolean is satisfied if a subset from the numbers sum up to less than or equal to . What is the maximum number of booleans that can be satisfied?
Note: the empty subset sums up to 0.
Input Specification
On the first line, there are two integers , and , separated by a space.
On the second line is a space separated list of the integers.
Each line is followed by one line feed character (ASCII code 0x0a).
There are no trailing spaces or empty lines.
Output Specification
One integer, the number of subsets that sum to less than or equal to .
Constraints
For all subtasks:
For all subset sums ,
For 2 of the 15 available marks,
Sample Input 1
10 10
8 2 10 10 6 1 10 10 1 5
Sample Output 1
33
Sample Input 2
5 5
1 2 3 4 5
Sample Output 2
10
Comments