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.
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.
One integer, the number of subsets that sum to less than or equal to .
For all subtasks:
For all subset sums, , .
Subtask 1 [2/15]
Subtask 2 [7/15]
Subtask 3 [6/15]
No additional constraints.
Sample Input 1
10 10 8 2 10 10 6 1 10 10 1 5
Sample Output 1
Sample Input 2
5 5 1 2 3 4 5
Sample Output 2