Page not loading? Try clicking here.
Placeholder

#10407

Retiling 40s 1024MB

Problems

Cody-Jamal's latest artistic installment is a tiled kitchen floor that can be retiled to different patterns. The floor consists of a matrix of \mathbf{R} rows and \mathbf{C} columns of square tiles. Each tile is reversible, one side is magenta and the other one is green.

To retile the kitchen, there are two allowed operations:

  • flip a tile, changing its visible color from magenta to green, or vice versa, and
  • swap two adjacent tiles (horizontally or vertically, but not diagonally), without flipping either.

Viewing Cody-Jamal's artistic floor is free, but interacting with it is not. Performing a single flip operation costs \mathbf{F} coins, and performing a single swap operation costs \mathbf{S} coins.

You can see the current state of the floor and want to turn it into a particular pattern. What is the minimum amount of coins you need to spend to achieve your goal?


Input

The first line of the input gives the number of test cases, \mathbf{T}. \mathbf{T} test cases follow. The first line of a test case contains 4 integers: \mathbf{R}, \mathbf{C}, \mathbf{F} and \mathbf{S}, the number of rows and columns of the floor, the cost in coins of flipping and the cost in coins of swapping, respectively. Then, 2 \cdot \mathbf{R} lines follow. The first \mathbf{R} lines contain \mathbf{C} characters each. The j⁠-th character of the i⁠-th of these lines represents the current state of the tile in the i⁠-th row and j⁠-th column. The character is M if the currently visible side is magenta and G otherwise. The last \mathbf{R} lines also contain \mathbf{C} characters each. The j⁠-th character of the i⁠-th of these lines represents the color you want for the tile in the i⁠-th row and j⁠-th column, using the same character code as for the current state.


Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum amount of coins you need to spend to perform operations that allow you to change the tile colors from their current state to your intended one.


Example #1

2
2 4 1 1
MGMG
MMMG
GMGM
MMMM
3 3 1 1
MGG
GMG
MMM
MMM
MGM
MMG
Case #1: 3
Case #2: 4
In the Sample Case for Test Set 2, flips are so expensive that we want to avoid them at all costs. We need at least one since our desired floor state has more magenta tiles than the current one, and swaps do not change that amount. We can do it optimally with just one flip like this: Swap the leftmost two tiles. Flip the rightmost tile. Swap the second and third tiles from the left. Swap the third and fourth tiles from the left. The picture below illustrates all the states the floor goes through.

Example #2

1
1 5 1000 1
MGGGG
GGGMM
Case #1: 1003

Source

GCJ 2021r2 D

You must sign in to write code.