AT_abc184_f [ABC184F] Programming Contest

题目描述

高桥君要参加一场编程竞赛。该竞赛的比赛时间为 $T$ 分钟，共有 $N$ 道题目。
由于高桥君拥有超能力，他知道第 $i$ 道题目可以在 $A_i$ 分钟内解答完毕。
高桥君可以从 $N$ 道题目中选择 $0$ 道或多道题目，使得解答所需的总时间不超过 $T$ 分钟，并解答这些题目。
请你求出所选题目解答所需总时间的最大值。

输入格式

输入以如下格式从标准输入读入。

$N$ $T$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出一个整数，表示最大可能的总时间。

输入输出样例 #1

输入 #1

5 17
2 3 5 7 11

输出 #1

17

输入输出样例 #2

输入 #2

6 100
1 2 7 5 8 10

输出 #2

33

输入输出样例 #3

输入 #3

6 100
101 102 103 104 105 106

输出 #3

0

输入输出样例 #4

输入 #4

7 273599681
6706927 91566569 89131517 71069699 75200339 98298649 92857057

输出 #4

273555143

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 40$
• $1 \leq T \leq 10^9$
• $1 \leq A_i \leq 10^9$

样例解释 1

选择第 $1,2,3,4$ 道题目时，总用时为 $2+3+5+7=17$ 分钟，正好等于 $T=17$，这是不超过 $T$ 的最大值。

样例解释 2

选择所有题目是最优解。

样例解释 3

无法选择任何题目。

样例解释 4

选择第 $2,3,7$ 道题目时，总用时为 $273555143$ 分钟。

由 ChatGPT 4.1 翻译