# Subset Sum

Time Limit: 10 Seconds Memory Limit: 131072 KB

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

There are multiple test cases in the input. Each test case starts with a line containing two non-negative integers 0≤n≤30 and 0≤t≤1000. 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

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

## Sample Input

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

## Sample Output

15 16509438Submit

Source: 11th Iran Nationwide Internet Contest