Description

Armin 正在玩一款由 Hemisphere Games 开发的物理益智游戏 Osmos。在这款游戏中，他控制一个“小球”（mote），在空间中移动并吞噬更小的小球。

英文中的 “mote” 意为微粒。在本游戏中，就是一个可以吞噬（或被吞噬）其他物体的东西！本题中的游戏思想与 Osmos 类似，但你无需玩过原作。

当 Armin 的小球吞噬了一个比自己小的小球后，他的小球体积会增加，增长量等于被吞噬小球的体积。此时，他的小球可能能吞噬更多的小球。例如：假设 Armin 的小球初始体积为 $10$，其余小球的体积分别为 $9$、$13$ 和 $19$。开始时，Armin 的小球只能吞噬体积为 $9$ 的小球。吞噬后，他的体积变为 $19$。接着，他只能吞噬体积为 $13$ 的小球。再吞噬后，体积为 $32$。这样，Armin 的小球就可以吞噬最后一个小球了。

注意，只有当另一个小球体积严格小于 Armin 的小球时，他才能吞噬它。如果体积相等，则无法吞噬。

你负责编写用于生成小球的程序，供 Armin 吞噬。程序已经生成了一些不同体积的小球，并生成了 Armin 的小球。不幸的是，给定 Armin 的小球体积和其他小球的体积，有可能无法让 Armin 吞噬所有其他小球。

你需要解决这个问题。你可以进行两种操作，顺序和次数不限：你可以向游戏中添加一个任意正整数体积的小球，或者你可以移除已存在的任意一个小球。请问，最少需要多少次操作才能使 Armin 的小球能够吞噬所有其他小球？

例如，假设 Armin 的小球体积为 $10$，其余小球体积为 $[9, 20, 25, 100]$。此时无法全部吞噬，但你可以添加一个体积为 $3$ 的小球，并移除体积为 $100$ 的小球，仅需 $2$ 次操作即可使问题变得可解。此时答案为 $2$。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含 Armin 的小球体积 $A$ 和其他小球数量 $N$。第二行包含 $N$ 个整数，表示其他小球的体积。所有小球体积均为整数。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是使问题可解所需的最少操作次数。

4
2 2
2 1
2 4
2 1 1 6
10 4
25 20 9 100
1 4
1 1 1 1

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 4

Hint

样例说明

虽然输入文件中给定的小球体积有限，但 Armin 的小球在吞噬其他小球后体积可能会超过输入中的限制。

限制条件

• $1 \leq T \leq 100$

小数据集（10 分，测试集 1 - 可见）

• $1 \leq A \leq 100$
• $1 \leq$ 所有小球体积 $\leq 100$
• $1 \leq N \leq 10$

大数据集（12 分，测试集 2 - 隐藏）

• $1 \leq A \leq 10^6$
• $1 \leq$ 所有小球体积 $\leq 10^6$
• $1 \leq N \leq 100$

翻译由 ChatGPT-4.1 完成。