Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. The Values You Can Make

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPari wants to buy an expensive chocolate from Arya. She has *n* coins, the value of the *i*-th coin is *c*_{i}. 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 *c*_{1}, *c*_{2}, ..., *c*_{n} (1 ≤ *c*_{i} ≤ 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

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/31/2023 12:34:32 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|