题目描述

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

输入格式

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

$N$ $T$ $A_1$ $\dots$ $A_N$

输出格式

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

题目大意

给定 $N$ 个数，在数组中选任意个数，使得它们的总和不超过 $T$ 且最大。

5 17
2 3 5 7 11

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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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