Retiling

Cody-Jamal이 이번에 선보인 작품은 다양한 무늬로 다시 깔 수 있는 타일로 된 주방 바닥이다. 바닥은 R개의 행과 C개의 열로 이루어진 정사각형 타일 행렬이다. 타일은 양면을 뒤집어 쓸 수 있는데, 한쪽 면은 자홍색이고 다른 쪽 면은 초록색이다.

주방 바닥을 다시 깔기 위해 허용되는 연산은 두 가지다.

• 타일 한 장을 뒤집어 보이는 색을 자홍색에서 초록색으로, 또는 그 반대로 바꾼다.
• 서로 인접한 두 타일을 뒤집지 않고 맞바꾼다. 인접함은 가로 또는 세로 방향을 뜻하며 대각선 방향은 해당하지 않는다.

Cody-Jamal의 작품을 감상하는 것은 무료지만, 작품을 직접 건드리는 데는 돈이 든다. 뒤집기 연산 한 번에 F코인, 맞바꾸기 연산 한 번에 S코인이 든다.

현재 바닥의 상태를 보고 있으며, 이를 특정 무늬로 만들고자 한다. 목표를 이루기 위해 써야 하는 최소 코인 수는 얼마인가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 4개의 정수 R, C, F, S가 주어지는데, 각각 바닥의 행 수와 열 수, 뒤집기 연산에 드는 코인 비용, 맞바꾸기 연산에 드는 코인 비용이다. 그 뒤로 2⋅R개의 줄이 이어진다. 처음 R개의 줄은 각각 C개의 문자를 포함한다. 이 중 i번째 줄의 j번째 문자는 i번째 행 j번째 열에 있는 타일의 현재 상태를 나타낸다. 현재 보이는 면이 자홍색이면 M, 그렇지 않으면 G이다. 마지막 R개의 줄도 각각 C개의 문자를 포함한다. 이 중 i번째 줄의 j번째 문자는 i번째 행 j번째 열에 있는 타일에 원하는 색을 나타내며, 현재 상태와 같은 문자 체계를 쓴다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 타일 색을 현재 상태에서 원하는 상태로 바꾸기 위해 수행해야 하는 연산에 드는 최소 코인 수이다.

• 1 ≤ T ≤ 100.
• 1 ≤ R ≤ 10.
• 1 ≤ C ≤ 10.