子集和问题的近似算法

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description



对于给定的子集和问题的一个实例〈S,t〉,设计一个算法找出S的一个子集S1,使得其和不超过t,又尽可能地接近t。

Input

输入数据的第1 行有2 个正整数n和t(n<30,t<150),n表示S的大小,t 是子集和的目标值。接下来的1行中,有n个正整数,表示集合S中的元素。

Output

将子集和的最优值输出。

Sample Input

3 7
1 4 5

Sample Output

6

Hint

 

Source