Cody-Jamal 的最新艺术装置是一个可以重新铺设成不同图案的瓷砖厨房地板。地板由 $R$ 行 $C$ 列的方形瓷砖矩阵组成。每块瓷砖都是可翻转的，一面是品红色，另一面是绿色。

要重新铺设厨房，有两种允许的操作： 翻转一块瓷砖，将其可见颜色从品红色变为绿色，反之亦然； 交换两块相邻的瓷砖（水平或垂直，不能对角线），且不翻转它们。

观看 Cody-Jamal 的艺术地板是免费的，但与之交互则不然。执行一次翻转操作的成本为 $F$ 个硬币，执行一次交换操作的成本为 $S$ 个硬币。

你可以看到地板的当前状态，并希望将其变为特定的图案。为了达到你的目标，你需要花费的最少硬币数量是多少？

输入格式

输入的第一行给出测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含 4 个整数：$R$、$C$、$F$ 和 $S$，分别代表地板的行数、列数、翻转的成本和交换的成本。接下来有 $2 \cdot R$ 行。前 $R$ 行每行包含 $C$ 个字符。这些行中第 $i$ 行的第 $j$ 个字符表示第 $i$ 行第 $j$ 列瓷砖的当前状态。如果当前可见面是品红色，则字符为 M，否则为 G。最后 $R$ 行也每行包含 $C$ 个字符。这些行中第 $i$ 行的第 $j$ 个字符表示你希望第 $i$ 行第 $j$ 列瓷砖呈现的颜色，使用与当前状态相同的字符编码。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你为了将瓷砖颜色从当前状态更改为目标状态所需执行操作的最少硬币花费。

数据范围

$1 \le T \le 100$ $1 \le R \le 10$ $1 \le C \le 10$ $1 \le F \le 10^6$ $1 \le S \le 10^6$

样例

样例输入 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

说明

在样例 1 中，有 5 块瓷砖在当前状态和目标状态之间的颜色不同。由于每次操作最多可以改变 2 块瓷砖，因此至少需要 3 次操作，花费 3 个硬币。一种恰好花费 3 个硬币的方法是： 1. 交换顶行最左侧的两块瓷砖。 2. 交换顶行最右侧的两块瓷砖。 3. 翻转右下角的瓷砖。

在样例 2 中，有 6 块瓷砖需要改变。然而，由于只有交换操作可以同时改变两块瓷砖，如果只用交换操作，则需要 3 次操作。没有办法让所有 6 块瓷砖各参与一次交换，因此我们至少需要 4 次操作。一种恰好花费 4 个硬币的方法是： 1. 交换中间列最上方的两块瓷砖。 2. 翻转右上角的瓷砖。 3. 交换最右列最下方的两块瓷砖。 4. 翻转最左列中间的瓷砖。

样例输入 2

1
1 5 1000 1
MGGGG
GGGMM

样例输出 2

Case #1: 1003

说明

在测试集 2 的样例中，翻转操作非常昂贵，因此我们尽量避免使用。由于我们的目标地板状态比当前状态有更多的品红色瓷砖，而交换操作不会改变品红色瓷砖的总数，因此我们至少需要一次翻转。我们可以通过仅进行一次翻转来达到最优解： 1. 交换最左侧的两块瓷砖。 2. 翻转最右侧的瓷砖。 3. 交换从左侧数第二和第三块瓷砖。 4. 交换从左侧数第三和第四块瓷砖。

Figure 1. 样例 1 的操作步骤演示