타일 다시 깔기

Cody-Jamal의 최신 예술 작품은 여러 무늬로 타일을 다시 깔 수 있는 주방 바닥이다. 바닥은 정사각형 타일로 이루어진 $\mathbf{R}$행 $\mathbf{C}$열의 행렬이다. 각 타일은 뒤집을 수 있으며, 한쪽 면은 자홍색이고 다른 쪽 면은 초록색이다.

주방의 타일을 다시 깔기 위해 다음 두 가지 연산이 허용된다.

• 타일 하나를 뒤집어 보이는 색을 자홍색에서 초록색으로, 또는 그 반대로 바꾼다.

• 서로 인접한 두 타일을 어느 쪽도 뒤집지 않고 교환한다. 타일은 가로나 세로로 인접해야 하며 대각선으로 인접해서는 안 된다.

Viewing Cody-Jamal의 예술적인 바닥은 무료지만, 바닥에 손을 대는 데에는 비용이 든다. 뒤집기 연산을 한 번 수행하는 데에는 $\mathbf{F}$개의 동전이 들고, 교환 연산을 한 번 수행하는 데에는 $\mathbf{S}$개의 동전이 든다.

바닥의 현재 상태를 볼 수 있으며, 이를 특정 무늬로 바꾸려고 한다. 목표를 달성하기 위해 사용해야 하는 동전의 최소 개수는 얼마인가?

제한

시간 제한: 40초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{R} \le 10$. $1 \le \mathbf{C} \le 10$.

테스트 세트 1 (Visible Verdict)

$\mathbf{F} = 1$. $\mathbf{S} = 1$.

테스트 세트 2 (Hidden Verdict)

$1 \le \mathbf{F} \le 10^6$. $1 \le \mathbf{S} \le 10^6$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 4개의 정수 $\mathbf{R}$, $\mathbf{C}$, $\mathbf{F}$, $\mathbf{S}$가 주어지며, 각각 바닥의 행 수, 열 수, 뒤집기에 드는 동전 수, 교환에 드는 동전 수를 나타낸다. 이어서 $2 \cdot \mathbf{R}$개의 줄이 주어진다. 이 중 처음 $\mathbf{R}$개의 줄은 각각 $\mathbf{C}$개의 문자를 포함한다. 이 줄들 중 $i$⁠번째 줄의 $j$⁠번째 문자는 $i$⁠번째 행과 $j$⁠번째 열에 있는 타일의 현재 상태를 나타낸다. 현재 보이는 면이 자홍색이면 문자는 M이고, 그렇지 않으면 G이다. 마지막 $\mathbf{R}$개의 줄도 각각 $\mathbf{C}$개의 문자를 포함한다. 이 줄들 중 $i$⁠번째 줄의 $j$⁠번째 문자는 $i$⁠번째 행과 $j$⁠번째 열의 타일에 원하는 색을 나타내며, 현재 상태와 같은 문자 코드를 사용한다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 타일의 색을 현재 상태에서 의도한 상태로 바꿀 수 있도록 연산을 수행하는 데 사용해야 하는 동전의 최소 개수이다.

예제 케이스 #1에서는 바닥의 현재 상태와 원하는 상태에서 색이 서로 다른 타일이 $5$개 있다. 각 연산으로 최대 $2$개의 타일을 바꿀 수 있으므로, 적어도 $3$번의 연산이 필요하며 비용은 $3$개의 동전이다. 정확히 $3$개의 동전을 사용해 이를 수행하는 한 가지 방법은 다음과 같다.

• 맨 위 행에서 가장 왼쪽의 타일 두 개를 교환한다.

• 맨 위 행에서 가장 오른쪽의 타일 두 개를 교환한다.

• 오른쪽 아래 모서리의 타일을 뒤집는다.

아래 그림은 바닥이 거치는 상태를 보여 준다. 각 상태에서 강조된 타일 하나 또는 여러 타일은 해당 연산으로 바뀌는 타일이다.

예제 케이스 #2에서는 바꿔야 하는 타일이 $6$개 있다. 하지만 한 번에 두 타일을 바꿀 수 있는 연산은 교환뿐이므로, $3$번의 연산으로 해결하려면 모든 연산이 교환이어야 한다. $6$개의 모든 타일을 각각 단 한 번의 교환에 참여시키는 방법은 없으므로 적어도 $4$번의 연산이 필요하다. 정확히 $4$번의 연산을 사용하는 한 가지 방법은 다음과 같다.

• 가운데 열에서 가장 위쪽의 타일 두 개를 교환한다.

• 오른쪽 위 모서리의 타일을 뒤집는다.

• 가장 오른쪽 열에서 가장 아래쪽의 타일 두 개를 교환한다.

• 가장 왼쪽 열의 가운데 타일을 뒤집는다.

아래 그림은 바닥이 거치는 상태를 보여 준다.

추가 예제 - 테스트 세트 2

테스트 세트 2의 예제 케이스에서는 뒤집기의 비용이 매우 비싸므로 어떤 대가를 치르더라도 피하려고 한다. 원하는 바닥 상태에는 현재 상태보다 자홍색 타일이 더 많고 교환은 그 수를 바꾸지 않으므로, 적어도 한 번은 뒤집어야 한다. 다음과 같이 단 한 번만 뒤집어 최적으로 수행할 수 있다.

• 가장 왼쪽의 타일 두 개를 교환한다.

• 가장 오른쪽 타일을 뒤집는다.

• 왼쪽에서 두 번째 타일과 세 번째 타일을 교환한다.

• 왼쪽에서 세 번째 타일과 네 번째 타일을 교환한다.

아래 그림은 바닥이 거치는 모든 상태를 보여 준다.