P13022 [GCJ 2021 Qualification] Moons and Umbrellas

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 以最小化成本的方式完成壁画，他需要支付多少版权费用？

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

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

**样例解释** 样例 #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 完成