2973. 卡片游戏

单点时限: 2.0 sec

内存限制: 256 MB

有一种称为 21 点的游戏,在一堆扑克牌中任选 3 张,使 3 张牌的点数的和尽可能大,但不能超过 21 点,否则就 “ 爆 ” 了。

现在这个游戏有了新玩法:扑克牌变成了标有数字的卡片,共有 N 张,从中选取 3 张,使得这 3 张卡片上的数字的和在不超过 M 的情况下尽可能大。

请你编写一个程序,选取 3 张卡片使得它们的和最大。

例如:有 5 张卡片,数字分别为 5、6、7、8、9,M 为 21 时选择 6、7、8,则不超 M 的最大和为 21。又如:有 10 张卡片,数字分别为 93、181、245、214、315、36、185、138、216、295,M 为 500 时选择 245、36、216,则不超 M 的最大和为 497。

输入格式

第 1 行:整数 () 为问题数

第 2 行:第一个问题中的

第 3 行:第一个问题中的 N 个数 (均为小于100000的正整数,以空格隔开)。

第 4 ∽ 2 * T+1 行:每两行是每一个问题的输入,格式与第一个问题相同。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等),然后在一行中输出最大和。

样例

Input
2
5 21
5 6 7 8 9
10 500
93 181 245 214 315 36 185 138 216 295
Output
case #0:
21
case #1:
497

430 人解决,484 人已尝试。

557 份提交通过,共有 1171 份提交。

1.4 EMB 奖励。

创建: 7 年,8 月前.

修改: 1 年,5 月前.

最后提交: 6 天,7 小时前.

来源: 2012年程序设计实践第9次上机考试