Problem B: Maximum Sum Subset

Memory Limit：128 MB Time Limit：0.350 S
Judge Style：Text Compare Creator：
Submit：11 Solved：7

Description

Given a set of n integers where n <= 40. Each of them is at most 1012 determine the maximum sum subset having sum less than or equal S where S <= 1018.

Input

First line, n & S, n: number of integers, S subset's sum.
Second line, n integers.

[Sample 1]
6 42
45 34 4 12 5 2

[Sample 2]
6 10
3 34 4 12 5 2

Output

One number, the maximum sum of subset.

[Sample 1]
41
Maximum possible subset sum is 41 which can be obtained by summing 34, 5 and 2.

[Sample 2]
10
Maximum possible subset sum is 10 which can be obtained by summing 2, 3 and 5.

Sample Input Copy 

6 42
45 34 4 12 5 2

Sample Output Copy 

41