题目描述

Cody-Jamal 最新的艺术装置是一个可以重新铺设不同图案的厨房瓷砖地面。地面由 $\mathbf{R}$ 行 $\mathbf{C}$ 列的正方形瓷砖组成。每块瓷砖都是双面的，一面是品红色（M），另一面是绿色（G）。

要重新铺设厨房地面，允许进行以下两种操作：

• 翻转一块瓷砖，将其可见面从品红色变为绿色，或反之，每次操作花费 $\mathbf{F}$ 枚硬币；
• 交换两块相邻的瓷砖（水平或垂直相邻，不包括对角线相邻），不翻转任何瓷砖，每次操作花费 $\mathbf{S}$ 枚硬币。

观看 Cody-Jamal 的艺术地面是免费的，但与之互动需要花费硬币。已知地面的当前状态和目标图案，求最少需要花费多少枚硬币才能将地面从当前状态转变为目标图案。

输入格式

输入第一行包含测试用例数量 $\mathbf{T}$。每个测试用例包含：

1. 第一行四个整数 $\mathbf{R}$、$\mathbf{C}$、$\mathbf{F}$、$\mathbf{S}$，分别表示地面的行数、列数、翻转操作的花费和交换操作的花费；
2. 接下来 $\mathbf{R}$ 行，每行 $\mathbf{C}$ 个字符，表示地面的当前状态（$\mathsf{M}$ 表示品红色，$\mathsf{G}$ 表示绿色）；
3. 最后 $\mathbf{R}$ 行，每行 $\mathbf{C}$ 个字符，表示目标图案（字符编码与当前状态相同）。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将地面转变为目标图案所需的最小硬币花费。

输入输出样例 #1

输入 #1

2
2 4 1 1
MGMG
MMMG
GMGM
MMMM
3 3 1 1
MGG
GMG
MMM
MMM
MGM
MMG

输出 #1

Case #1: 3
Case #2: 4

输入输出样例 #2

输入 #2

1
1 5 1000 1
MGGGG
GGGMM

输出 #2

Case #1: 1003

说明/提示

样例解释

在样例 #1 中：

• 当前状态与目标图案有 5 处颜色不同；
• 最少需要 3 次操作（每次操作最多改变 2 处颜色）；
• 一种最优方案：
  1. 交换第一行最左两块瓷砖；
  2. 交换第一行最右两块瓷砖；
  3. 翻转右下角瓷砖。

在样例 #2 中：

• 有 6 处颜色需要改变；
• 由于只能通过交换同时改变两处颜色，最少需要 4 次操作；
• 一种最优方案：
  1. 交换中间列最上两块瓷砖；
  2. 翻转右上角瓷砖；
  3. 交换最右列最下两块瓷砖；
  4. 翻转最左列中间瓷砖。

测试集 2 的样例中：

• 翻转操作非常昂贵，应尽量避免；
• 由于目标图案比当前状态多 1 块品红色瓷砖，必须至少进行 1 次翻转；
• 最优方案（花费 1003 枚硬币）：
  1. 交换最左两块瓷砖；
  2. 翻转最右瓷砖；
  3. 交换左数第二和第三块瓷砖；
  4. 交换左数第三和第四块瓷砖。

限制条件

• $1 \leq \mathbf{T} \leq 100$；
• $1 \leq \mathbf{R} \leq 10$；
• $1 \leq \mathbf{C} \leq 10$。

测试集 1（11 分，可见判定）

• $\mathbf{F}=1$；
• $\mathbf{S}=1$。

测试集 2（23 分，隐藏判定）

• $1 \leq \mathbf{F} \leq 10^{6}$；
• $1 \leq \mathbf{S} \leq 10^{6}$。