Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 00:30:17 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|