配点 : $600$ 点

問題文

高橋くんはプログラミングコンテストに参加します。 このコンテストのコンテスト時間は $T$ 分間で、 $N$ 問の問題が出題されます。 高橋くんは超能力者なので、 $i$ 番目の問題が $A_i$ 分で解けることが分かっています。 高橋くんは $N$ 問の中から $0$ 問以上を、解くのにかかる時間の総和が $T$ 分以下になるように選び、それらの問題を解きます。 選んだ問題を解くのにかかる時間の総和の最大値を求めてください。

制約

• 入力は全て整数
• $1 \le N \le 40$
• $1 \le T \le 10^9$
• $1 \le A_i \le 10^9$

入力

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

$N$ $T$

$A_1$ $\dots$ $A_N$

出力

答えを整数として出力せよ。

5 17
2 3 5 7 11

17

$1,2,3,4$ 問目を選ぶと、解くのにかかる時間の総和が $2+3+5+7=17$ 分となり、 $T=17$ 分以下での最大になります。

6 100
1 2 7 5 8 10

33

全ての問題を解くのが最適です。

6 100
101 102 103 104 105 106

0

どの問題も解くことができません。

7 273599681
6706927 91566569 89131517 71069699 75200339 98298649 92857057

273555143

$2,3,7$ 問目を選ぶと、解くのにかかる時間の総和が $273555143$ 分になります。