分数: 600 点
问题陈述
高桥将参加编程竞赛,持续时间 T 会议记录和礼物 N 问题。
以他的超感官知觉,他已经知道这需要 A_i 分钟解决 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
输出
将答案打印为整数。
示例输入 1
5 17 2 3 5 7 11
示例输出 1
17
如果他选择 1-st, 2-nd, 3-rd,和 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-nd, 3-rd,和 7第一个问题,需要他 273555143 分钟。