ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4689: 你可以创造的价值

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：6 通过：6
提交提交记录统计Web Board

题目描述


     zz想从艾莉那里买一块昂贵的巧克力。zz的零钱罐里有n枚硬币，第i枚硬币的价值是ci。巧克力的价格是k，zz打算从零钱罐里选出若干硬币，选出的硬币的和等于k，然后项艾莉购买巧克力。

     看着选出的硬币，zz想到了一个问题：在把硬币交给艾莉之后，艾莉能用这些硬币创造多少个值呢？她想知道所有的值x，这样艾莉就可以用一些硬币的子集和k来做x。

     从形式上讲，zz想知道的值x，就是zz从n个硬币选出价值为k的若干硬币，问从这些硬币中组合成k的集合的子集合中又能组成多少个数、




Pari wants to buy an expensive chocolate from Arya. She has n coins, the value of the i-th coin is ci. The price of the chocolate is k, so Pari will take a subset of her coins with sum equal to k and give it to Arya.
Looking at her coins, a question came to her mind: after giving the coins to Arya, what values does Arya can make with them? She is jealous and she doesn't want Arya to make a lot of values. So she wants to know all the values x, such that Arya will be able to make x using some subset of coins with the sum k.
Formally, Pari wants to know the values x such that there exists a subset of coins with the sum k such that some subset of this subset has the sum x, i.e. there is exists some way to pay for the chocolate, such that Arya will be able to make the sum x using these coins.
Input
The first line contains two integers n and k (1≤n,k≤500)− the number of coins and the price of the chocolate, respectively.
Next line will contain n integers c1,c2,...,cn (1≤ci≤500)− the values of Pari's coins.
It's guaranteed that one can make value k using these coins.
Output
First line of the output must contain a single integer q− the number of suitable values x. Then print q integers in ascending order− the values that Arya can make for some subset of coins of Pari that pays for the chocolate.
Examples

输入格式

第一行包含两个整数n和k（1≤n、 k个≤500)− 硬币的数量和巧克力的价格。

下一行将包含n个整数c1、c2、…、cn（1≤ci公司≤500)表示巴黎硬币的价值。

可以保证使用这些硬币可以获得k值。

输出格式

输出的第一行必须包含单个整数q为合适值x的数量。然后按升序输出q个整数，为艾莉可以为zz支付巧克力的硬币的某个子集创造的值。

示例

输入

6 18

5 6 1 10 12 2

输出

16

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



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

输入样例 复制 

6 18
5 6 1 10 12 2

输出样例 复制 

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

分类标签