Aquarium

Your aquarium is divided into a grid of $R$ rows and $C$ columns, and every cell holds one slanted wall. A wall either joins the bottom-left corner of its cell to the top-right corner (/) or joins the top-left corner to the bottom-right corner (\). The outer border of the aquarium is glass and can never be taken down.

The walls cut the interior into compartments. Two points lie in the same compartment when a fish can swim from one to the other without crossing a wall. Two walls that touch at a single point still block that point.

Each cell records the strength of the wall inside it, and taking that wall down costs exactly its strength. A wall comes down whole. Find the smallest total strength needed to turn the whole interior into one compartment.

The picture below shows a $2 \times 2$ aquarium. It has four compartments, and taking down the walls of strength 7, 9 and 12 leaves a single compartment. Nothing cheaper than 28 works.

The first line contains the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case contains the number of rows $R$ and the number of columns $C$ ($1 \le R, C \le 100$).

The next $R$ lines describe the walls. Each line holds $C$ characters with no spaces, and each character is / or \.

The next $R$ lines hold $C$ integers each. An integer is the strength of the wall in the matching cell, and it is between 1 and 10000.

For each test case print one line in the form Case x: y, where $x$ is the test case number starting at 1 and $y$ is the minimum total strength needed to make the interior one compartment.