P13223 [GCJ 2015 #1C] Less Money, More Problems

直到今天，你所在的国家一直使用 $\mathbf{D}$ 种不同面值的正整数硬币进行所有交易。今天，女王因一位臣民试图用一大袋低面值硬币缴税而大为光火，并下令：在任何一次购买中，每种面值的硬币最多只能使用 $\mathbf{C}$ 枚。例如，如果 $\mathbf{C} = 2$，现有的面值为 $1$ 和 $5$，那么可以用两个 $5$ 和一个 $1$ 买到价值 $11$ 的物品，或者用两个 $5$ 和两个 $1$ 买到价值 $12$ 的物品，但无法买到价值 $9$ 或 $17$ 的物品。 你无法直接挑战女王的命令，但你恰好负责铸币厂，可以发行新的硬币面值。你希望在女王新规定下，使得任意不超过 $\mathbf{V}$ 的正整数金额都能被购买（注意，在女王下令前，这可能并不总是可行）。此外，你希望新增的面值数量尽可能少，并且最终的面值集合（包括原有和新增）不能有重复。 请问，最少需要新增多少种面值？

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

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

**样例解释** 注意，样例中的第 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 翻译