eolymp
bolt
Try our new interface for solving problems
Problems

Subset Sum

Subset Sum

Time limit 1 second
Memory limit 64 MiB

For a given set X of n not-necessarily-distinct numbers and a given number t, the goal is to compute the number of non-empty subsets Y of X with the properties that the sum over all members of Y is at most t and adding any member in X-Y to Y makes the summation greater than t. Note that the numbers in the set may have the same values, but they must be considered inherently different.

Input data

There are multiple test cases in the input. Each test case starts with a line containing two non-negative integers 0n 30 and 0t1000. The remainder of each test case consists of one or more lines containing n non-negative numbers belonging to X. The input terminates with "0 0" which should not be processed.

Output data

For each test case, output the number of subsets defined above.

Examples

Input example #1
6 25
8 9 8 7 16 5
30 250
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
0 0
Output example #1
15
16509438
Source 2013 11th Iran Internet Programming Contest, November 28 (7 Azar, 1392)