Programming Contest

题目描述

Takahashi 将参加一个持续 $T$ 分钟并包含 $N$ 道题目的编程比赛。
凭借他的超感知能力，他已经知道解决第 $i$ 道题需要 $A_i$ 分钟。
他将从这 $N$ 道题中选择零道或多道题来做，使得他总共用时不超过 $T$ 分钟。
求他所选题目用时可能的最长时间。

输入格式

输入由标准输入给出，格式如下： $N$ $T$ $A_1$ $\dots$ $A_N$

输出格式

以整数形式输出答案。

5 17
2 3 5 7 11

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

提示

输入中的所有数值均为整数。 $1 \le N \le 40$ $1 \le T \le 10^9$ $1 \le A_i \le 10^9$如果他选择第 $1$、$2$、$3$ 和 $4$ 道题，则总用时为 $2+3+5+7=17$ 分钟，这是不超过 $T=17$ 分钟的最长可能时间。
最优策略是做全部题目。
他无法做任何题目。
如果他选择第 $2$、$3$ 和 $7$ 道题，则总用时为 $273555143$ 分钟。

标签: AtCoder|abc184F

来源

AtCoder|abc184F