/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを整数として出力せよ。
入力例 1
5 17 2 3 5 7 11
出力例 1
17
1,2,3,4 問目を選ぶと、解くのにかかる時間の総和が 2+3+5+7=17 分となり、 T=17 分以下での最大になります。
入力例 2
6 100 1 2 7 5 8 10
出力例 2
33
全ての問題を解くのが最適です。
入力例 3
6 100 101 102 103 104 105 106
出力例 3
0
どの問題も解くことができません。
入力例 4
7 273599681 6706927 91566569 89131517 71069699 75200339 98298649 92857057
出力例 4
273555143
2,3,7 問目を選ぶと、解くのにかかる時間の総和が 273555143 分になります。
Score : 600 points
Problem Statement
Takahashi will participate in a programming contest, which lasts for T minutes and presents N problems.
With his extrasensory perception, he already knows that it will take A_i minutes to solve the i-th problem.
He will choose zero or more problems to solve from the N problems so that it takes him no longer than T minutes in total to solve them.
Find the longest possible time it takes him to solve his choice of problems.
Constraints
- All values in input are integers.
- 1 \le N \le 40
- 1 \le T \le 10^9
- 1 \le A_i \le 10^9
Input
Input is given from Standard Input in the following format:
N T A_1 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
5 17 2 3 5 7 11
Sample Output 1
17
If he chooses the 1-st, 2-nd, 3-rd, and 4-th problems, it takes him 2+3+5+7=17 minutes in total to solve them, which is the longest possible time not exceeding T=17 minutes.
Sample Input 2
6 100 1 2 7 5 8 10
Sample Output 2
33
It is optimal to solve all the problems.
Sample Input 3
6 100 101 102 103 104 105 106
Sample Output 3
0
He cannot solve any of the problems.
Sample Input 4
7 273599681 6706927 91566569 89131517 71069699 75200339 98298649 92857057
Sample Output 4
273555143
If he chooses the 2-nd, 3-rd, and 7-th problems, it takes him 273555143 minutes in total to solve them.