AtCoder Beginner Contest 184
翻译中…
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.
翻译中…
样例
Input #1
5 17
2 3 5 7 11
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.
Input #2
6 100
1 2 7 5 8 10
Output #2
33
It is optimal to solve all the problems.
Input #3
6 100
101 102 103 104 105 106
Output #3
0
He cannot solve any of the problems.
Input #4
7 273599681
6706927 91566569 89131517 71069699 75200339 98298649 92857057
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.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。