题目描述

你的团队即将在斗舞中证明自己！最初，你的团队有 $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$ 是战斗结束时你能获得的最大荣誉。

2
100 1
100
10 3
20 3 15

Case #1: 0
Case #2: 1

提示

在样例 #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 完成