Description

直到今天，你所在的国家一直使用 $\mathbf{D}$ 种不同面值的正整数硬币进行所有交易。今天，女王因一位臣民试图用一大袋低面值硬币缴税而大为光火，并下令：在任何一次购买中，每种面值的硬币最多只能使用 $\mathbf{C}$ 枚。例如，如果 $\mathbf{C} = 2$，现有的面值为 $1$ 和 $5$，那么可以用两个 $5$ 和一个 $1$ 买到价值 $11$ 的物品，或者用两个 $5$ 和两个 $1$ 买到价值 $12$ 的物品，但无法买到价值 $9$ 或 $17$ 的物品。

你无法直接挑战女王的命令，但你恰好负责铸币厂，可以发行新的硬币面值。你希望在女王新规定下，使得任意不超过 $\mathbf{V}$ 的正整数金额都能被购买（注意，在女王下令前，这可能并不总是可行）。此外，你希望新增的面值数量尽可能少，并且最终的面值集合（包括原有和新增）不能有重复。

请问，最少需要新增多少种面值？

Input Format

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例包含两行，第一行为三个用空格分隔的整数 $\mathbf{C}$、$\mathbf{D}$ 和 $\mathbf{V}$，第二行为 $\mathbf{D}$ 个升序排列的不同整数，表示已有的硬币面值。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 表示所需新增的最少面值数量。

4
1 2 3
1 2
1 3 6
1 2 5
2 1 3
3
1 6 100
1 5 10 25 50 100

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

Hint

样例解释

注意，样例中的第 3 和第 4 组数据不在 Small 数据集的限制范围内。

在第 1 组中，已经可以用现有的面值（每种最多用一枚）组合出所有需要的金额（$1, 2, 3$）。

在第 2 组中，只需新增面值 $3$ 或 $4$ 中的任意一个即可——无论选择哪一个，只需新增一种面值。

在第 3 组中，最优解是新增面值 $1$。

数据范围

• $1 \leq \mathbf{T} \leq 100$。
• 每种已有面值 $\leq \mathbf{V}$。

Small 数据集（11 分）

• 时间限制：240 5 秒。
• $\mathbf{C} = 1$。
• $1 \leq \mathbf{D} \leq 5$。
• $1 \leq \mathbf{V} \leq 30$。

Large 数据集（23 分）

• 时间限制：480 10 秒。
• $1 \leq \mathbf{C} \leq 100$。
• $1 \leq \mathbf{D} \leq 100$。
• $1 \leq \mathbf{V} \leq 10^9$。

由 ChatGPT 4.1 翻译