子集和问题完全多项式时间近似算法

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description



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

Input

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

Output

将子集和的最优值输出。第1 行是n 和t 的值。第2 行是计算出的近似最优值。

Sample Input

17 100
10 8 8 5 5 6 3 6 2 9 2 10 10 4 9 3 6

Sample Output

17 100
100

Hint

 

Source