编程竞赛

题目描述

高桥君要参加编程竞赛。这场竞赛的比赛时间为 $T$ 分钟，共出 $N$ 道题。

高桥君是超能力者，所以知道第 $i$ 道题可以在 $A_i$ 分钟内解出。

高桥君从 $N$ 道题中选择 $0$ 道或更多道题，使解题所需时间的总和不超过 $T$ 分钟，然后解这些题。

请计算所选问题解题所需时间总和的最大值。

输入格式

输入按以下格式从标准输入给出：

$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$ 分钟。

数据范围

• 输入均为整数
• $1 \le N \le 40$
• $1 \le T \le 10^9$
• $1 \le A_i \le 10^9$