X

N

i

w_i

N

X

入力は以下の形式で標準入力から与えられる。

N X
w_1
w_2
:
w_N

• $1$ 行目には、品物の個数を表す整数 $N (1 \leq N \leq 32)$ とナップサックの大きさを表す整数 $X (1 \leq X \leq 10^9)$ が半角空白区切りで与えられる。
• $2$ 行目から $N$ 行では、品物の大きさが与えられる。このうち $i (1 \leq i \leq N)$ 行目には、$i$ 番目の品物の大きさを表す整数 $w_i (1 \leq w_i \leq 5 \times 10^7)$ が書かれている。

N

X

5 5
1
1
2
3
4

4

4

• 品物 $1$, 品物 $2$, 品物 $4$ を選ぶ: $1 + 1 + 3 = 5$
• 品物 $1$, 品物 $5$ を選ぶ: $1 + 4 = 5$
• 品物 $2$, 品物 $5$ を選ぶ: $1 + 4 = 5$
• 品物 $3$, 品物 $4$ を選ぶ: $2 + 3 = 5$

1

2

8 21
10
4
2
30
22
20
8
14

0

21

20 100000000
35576749
38866484
6624951
39706038
11133516
25490903
14701702
17888322
14423251
32111678
24509097
43375049
35298298
21158709
30489274
37977301
19510726
28841291
10293962
12022699

45

16 8
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

12870