Aquarium

There were different types of fish in your aquarium. But they did not go along well with each other. So there had been Fish War 1 among them. It was a complete mess. A lot of fish died, many of them hid in some mountain, some were eaten by other fish, and so on. So you decided to compartmentalize your aquarium. You divided your aquarium into an R × C grid, that is, R rows and C columns. Then you inserted walls into each cell. The walls are slanted, that is, they go from the northeast corner to the southwest corner or from the northwest corner to the southeast corner. They look like “/” or “\” respectively. Many years passed since the war. Now the fish want to unite again. They want to bring down the walls. They measured the strength of each of the walls. What is the minimum amount of strength they need to unite all the compartments?

For example, in the following 2 × 2 grid, they need 7 + 9 + 12 = 28 units of strength to unite the 4 compartments. And this is the minimum.

Input Specification

The first line of the input contains the number of test cases T (T ≤ 20). Then T test cases follow.

The first line of each test case describes the number of rows R and the number of columns C (1 ≤ R, C ≤ 100). The next R lines describe the walls. Each of these lines contains C characters, and the characters are either “/” or “\”. The next R lines contain C positive integers, each describing the strength of the wall at the corresponding cell. The strength of a wall will be at most 10 000.

Output Specification

For each test case, output the case number and the minimum amount of strength needed to unite all the compartments in the aquarium.

Sample Input

1. 2
2. 2 2
3. \/
4. \\
5. 7 10
6. 12 9
7. 1 3
8. /\\
9. 3 4 5

download as text file

Output for Sample Input

1. Case 1: 28
2. Case 2: 12

download as text file