P16632 [GKS 2017 #F] Dance Battle

你的团队即将在斗舞中证明自己！最初，你的团队有 $E$ 点能量，以及 $0$ 点荣誉。有 $N$ 个对手团队你必须面对；这些团队按顺序排列，第 $i$ 个团队的舞技为 $S_i$。 在每一轮战斗中，你将面对队列中的下一个对手团队，并且可以执行以下操作之一： 1. **斗舞**：你的团队损失等于对手团队舞技的能量，该对手团队不会回到队列中。你获得 $1$ 点荣誉。如果此操作会使你的能量降至 $0$ 或以下，则不能执行。 2. **拖延**：你找借口（“我们的鞋带还没系好！”），对手团队回到队列末尾。你的能量和荣誉不变。 3. **休战**：你与对手团队宣布休战，该对手团队不会回到队列中。你的能量和荣誉不变。 4. **招募**：你将对手团队招募到己方队伍中，该对手团队不会回到队列中。你的团队获得等于对手团队舞技的能量，但你失去 $1$ 点荣誉。如果此操作会使你的荣誉降至 $0$ 以下，则不能执行。 当队列中没有对手团队时，战斗结束。如果你做出最优决策，战斗结束时你能获得的最大荣誉是多少？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例；每个测试用例由两行组成。第一行包含两个整数 $E$ 和 $N$：你团队的能量以及对手团队的数量。第二行包含 $N$ 个整数 $S_i$；其中第 $i$ 个整数表示战斗开始时队列中第 $i$ 个对手团队的舞技。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是战斗结束时你能获得的最大荣誉。

在样例 #1 中，只有一个对手团队。你无法与他们斗舞，因为那样会使你的能量降至 $0$；你也无法招募他们，因为那样会使你的荣誉降至 $0$ 以下。拖延也无济于事，因此唯一的选择是宣布休战。你最终获得 $0$ 荣誉。 在样例 #2 中，一种最优策略是： 1. 对第一个对手团队拖延。他们回到队列末尾。 2. 与第二个对手团队斗舞。你的能量降至 $7$，荣誉增至 $1$。 3. 招募第三个对手团队。你的能量增至 $22$，荣誉降至 $0$。 4. 与第一个对手团队（此时又回到队首）斗舞。你的能量降至 $2$，荣誉增至 $1$。 你最终获得 $1$ 点荣誉。 ### 限制条件 $1 \le T \le 100$。 $1 \le E \le 10^6$。 对于所有 $i$，$1 \le S_i \le 10^6$。 **小数据集（测试集 1 – 可见）** $1 \le N \le 5$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 1000$。 翻译由 DeepSeek V4 Pro 完成