单点时限: 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 行:整数 $T$ ($1 \le T \le 10$) 为问题数
第 2 行:第一个问题中的 $N (3\leqslant N \leqslant 100) 和 M(10 \leqslant M \leqslant 30000)。$
第 3 行:第一个问题中的 N 个数 (均为小于100000的正整数,以空格隔开)。
第 4 ∽ 2 * T+1 行:每两行是每一个问题的输入,格式与第一个问题相同。
对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0:
等),然后在一行中输出最大和。
2 5 21 5 6 7 8 9 10 500 93 181 245 214 315 36 185 138 216 295
case #0: 21 case #1: 497