题面
有一种称为 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:
等),然后在一行中输出最大和。
样例
输入
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