← 返回题目列表

Codeforces · 687/C

C. 你可以创造的价值

中文机器翻译题面 查看原题

帕丽想从艾莉亚那里购买一块昂贵的巧克力。她有n枚硬币,第i枚硬币的价值是ci。巧克力的价格为 k,因此 Pari 会将其总金额等于 k ​​的硬币子集交给 Arya。

看着她的硬币,她想到了一个问题:将硬币交给Arya后,Arya可以用它们创造什么价值?她很嫉妒,她不希望艾莉亚做出太多的价值观。所以她想知道所有的值 x,这样 Arya 就能够使用总和为 k 的硬币子集来生成 x。

正式地,Pari 想知道值 x,以便存在总和为 k 的硬币子集,使得该子集的某个子集具有总和 x,即存在某种方式来支付巧克力,这样 Arya 将能够使用这些硬币获得总和 x。

输入

第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 500)——分别是硬币的数量和巧克力的价格。

下一行将包含 n 个整数 c1, c2, ..., cn (1 ≤ ci ≤ 500) - Pari 硬币的值。

保证可以使用这些硬币赚取价值 k。

输出

输出的第一行必须包含一个整数 q — 合适值 x 的数量。然后按升序打印 q 个整数——Arya 可以为支付巧克力的 Pari 硬币的某些子集生成的值。

示例

输入 #1

6 18
5 6 1 10 12 2

输出 #1

16
0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18

输入 #2

3 50
25 25 50

输出 #2

3
0 25 50