Description

你是一家巧克力制造商的公关经理。不幸的是，由于顾客认为老板吝啬小气，公司的形象受到了影响。你希望通过提供免费的工厂参观和巧克力品尝来扭转这种印象。

然而，在新项目刚开始后，你就意识到老板的名声并非空穴来风：他只同意免费赠送巧克力，前提是你能将成本降到最低。要赠送的巧克力以每包 $P$ 块的形式提供。你本希望每个参观团都能打开新的一包，但老板坚持要求，如果上一组有剩余的巧克力，必须在为下一组服务前先用完这些剩余，之后才能打开新的一包。

例如，假设每包有 $P=3$ 块巧克力，某一参观团有 $5$ 人。你需要打开两包巧克力，每人分到一块，还会剩下一块。假设接下来又有一组 $6$ 人的参观团到来，他们会先拿到那块剩余的巧克力，然后你再打开两包新巧克力，分给剩下的人，这样又会剩下一块。如果之后有两个 $4$ 人的参观团，第一个团会拿到剩余的一块加上一包新开的巧克力，最后一个 $4$ 人团则需要打开两包新巧克力。注意，即使你打算立刻用完新开的巧克力，也不能在用完所有剩余之前打开新的一包。

在上述例子中，$4$ 个团中有 $2$ 个团（第一个和最后一个）拿到的都是新开的巧克力。其余 $2$ 个团则拿到了一部分新巧克力和一部分剩余巧克力。你知道发放剩余巧克力并不能改善老板吝啬的形象，但为了让老板同意这个项目，你不得不接受这个制度。尽管条件不利，你仍然致力于把工作做好。

现在有 $N$ 个参观团提出了申请，每个团都说明了将有多少人来参观工厂。参观团会一个接一个到来。你希望安排他们的到场顺序，使得拿到全新巧克力（没有剩余巧克力）的团数最多。你不能拒绝任何团，也不能让同一个团多次领取巧克力，并且必须保证每个人都正好拿到一块巧克力。

在上述例子中，如果顺序不是 $5, 6, 4, 4$，而是 $4, 5, 6, 4$，那么总共有 $3$ 个团（除了 $5$ 人团外）能拿到全新巧克力。对于这组团体来说，没有任何顺序能让所有团都只拿到新巧克力。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据包含两行。第一行包含两个整数 $N$（参观团数量）和 $P$（每包巧克力的块数）。第二行包含 $N$ 个整数 $G_1, G_2, \dots, G_N$，分别表示每个团的人数。

Output Format

对于每组测试数据，输出一行，格式为 Case #x: y，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 表示在最优安排下，能拿到全新巧克力的团数。

3
4 3
4 5 6 4
4 2
4 5 6 4
3 3
1 1 1

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

Hint

样例解释

样例 1 即题目描述中的例子。除了上文给出的最优顺序外，像 $6, 5, 4, 4$ 这样的顺序也能使拿到全新巧克力的团数最大，尽管具体哪些团拿到新巧克力可能不同。注意，我们只关心拿到全新巧克力的团数，而不是这些团的人数总和。

样例 2 中，团体和样例 1 相同，但每包有两块巧克力。在这种情况下，有多种顺序（如 $4, 4, 6, 5$）可以让所有团都拿到全新巧克力。

样例 3 中，所有团都是单人团，他们都会从同一包巧克力中领取。当然，只有第一个人能拿到刚开封的巧克力。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq N \leq 100$。
• $1 \leq G_i \leq 100$，对所有 $i$。

小数据范围（6 分，测试点 1 - 可见）

• 时间限制：5 秒。
• $2 \leq P \leq 3$。

大数据范围（10 分，测试点 2 - 隐藏）

• 时间限制：10 秒。
• $2 \leq P \leq 4$。

由 ChatGPT 4.1 翻译