题目描述

高桥将参加一个持续 $T$ 分钟、共有 $N$ 个问题的编程竞赛。
凭借他的超感知能力，他已经知道解决第 $i$ 个问题需要 $A_i$ 分钟。
他将选择解决零个或多个问题，使得他解决这些问题所需的总时间不超过 $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$ 分钟。