F - 编程竞赛

得分：$600$ 分

题目描述

Takahashi参加一个持续时间为$T$分钟的编程竞赛，里面有$N$个题目。
凭借他的超感知能力，他已经知道解决第$i$个问题需要$A_i$分钟。
他要从这$N$个问题中选择解决零个或更多个问题，以便在总共不超过$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$分钟。