Description

Cody-Jamal 正在创作他最新的抽象艺术作品：一幅由一排渐亏的月亮和闭合的雨伞组成的壁画。不幸的是，贪婪的版权流氓声称渐亏的月亮看起来像大写字母 C，而闭合的雨伞看起来像字母 J，并且他们拥有 CJ 和 JC 的版权。因此，每当壁画中出现 CJ 时，Cody-Jamal 必须支付 $\mathbf{X}$，而出现 JC 时则需支付 $\mathbf{Y}$。

Cody-Jamal 不愿让他们破坏自己的艺术，因此不会更改已经画好的部分。但他决定，可以通过策略性地填充尚未完成的空白部分来最小化版权费用。

例如，如果 CJ?CC? 表示壁画的当前状态，其中 C 代表渐亏的月亮，J 代表闭合的雨伞，而 ? 代表需要填充为渐亏月亮或闭合雨伞的空白部分。他可以将壁画完成为 CJCCCC、CJCCCJ、CJJCCC 或 CJJCCJ。第一种和第三种选择需要支付 $\mathbf{X} + \mathbf{Y}$ 的版权费用，而第二种和第四种则需要支付 $2 \cdot \mathbf{X} + \mathbf{Y}$。

给定费用 $\mathbf{X}$ 和 $\mathbf{Y}$ 以及一个表示壁画当前状态的字符串，如果 Cody-Jamal 以最小化成本的方式完成壁画，他需要支付多少版权费用？

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 行。每行包含两个整数 $\mathbf{X}$ 和 $\mathbf{Y}$ 以及一个字符串 $\mathbf{S}$，分别表示两项费用和壁画的当前状态。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Cody-Jamal 在完成壁画后需要支付的最小版权费用。

4
2 3 CJ?CC?
4 2 CJCJ
1 3 C?J
2 5 ??J???

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

1
2 -5 ??JJ??

Case #1: -8

Hint

样例解释

样例 #1 是题目描述中解释的情况。最小费用为 $\mathbf{X} + \mathbf{Y} = 2 + 3 = 5$。

在样例 #2 中，Cody-Jamal 已经完成了壁画，因此无法选择。壁画中有两个 CJ 和一个 JC。

在样例 #3 中，无论是将 ? 替换为 C 还是 J，都会在第二和第三个字符或第一和第二个字符之间形成一个 CJ。

在样例 #4 中，Cody-Jamal 可以将壁画全部填充为 J。由于这既不包含 CJ 也不包含 JC，因此不需要支付版权费用。

以下附加样例 2 符合测试集 3 的限制，但不会在提交的解决方案中运行。

在测试集 3 的样例 #1 中，Cody-Jamal 可以最优地将壁画完成为 JCJJCC 或 JCJJJC。无论哪种方式，壁画中都有一个 CJ 和两个 JC。

数据范围

• $1 \leq \mathbf{T} \leq 100$。
• $\mathbf{S}$ 中的每个字符为 $\mathbf{C}$、$\mathbf{J}$ 或 $\mathbf{?}$。

测试集 1（5 分，可见判定结果）

• $1 \leq \mathbf{S}$ 的长度 $\leq 10$。
• $1 \leq \mathbf{X} \leq 100$。
• $1 \leq \mathbf{Y} \leq 100$。

测试集 2（11 分，可见判定结果）

• $1 \leq \mathbf{S}$ 的长度 $\leq 1000$。
• $1 \leq \mathbf{X} \leq 100$。
• $1 \leq \mathbf{Y} \leq 100$。

额外奖励！

如果某些版权持有者反而会支付 Cody-Jamal 广告费而不是向他收费呢？Cody-Jamal 获得报酬的情况用负成本表示。

测试集 3（1 分，隐藏判定结果）

• $1 < \mathbf{S}$ 的长度 $< 1000$。
• $-100 \leq \mathbf{X} \leq 100$。
• $-100 \leq \mathbf{Y} \leq 100$。

翻译由 DeepSeek V3 完成