← 返回题目列表

AtCoder · abc184_f

F. 编程竞赛

中文机器翻译题面 查看原题

分数: 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 分钟。