Score : $600$ points

问题陈述

高桥将参加一个持续$T$分钟的编程比赛，并呈现$N$个问题。 凭借他的超能力感知，他已经知道解决第$i$个问题将需要$A_i$分钟。 他将从$N$个问题中选择零个或多个问题来解决，以便他解决这些问题的总时间不超过$T$分钟。 找出他解决所选问题的最长可能时间。

以上为大语言模型 kimi 翻译，仅供参考。

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.