Game on Chessboard

Given a chessboard of size n × n. The rows are numbered 1, 2,... , n from top to bottom while the columns are numbered 1, 2, ... , n from left to right, which means that (1, 1) is the top-left corner and that (n, n) is the bottom-right corner.
There are some chesses in the chessboard. Each chess has a color, white or black, and a cost value w. The number of chesses in one cell does not exceed 1.
You want to remove these chesses. In each time, you can choose one white chess u and one black chess v and then remove them with cost |wu u wv|. Moreover, one chess can be chosen in this operation if and only if there are no other chesses in its bottom-left area. Formally, one chess positioned at (x, y)
can be chosen if and only if there are no other chesses (x1, y1) that x1 ≥ x and y1 ≤ y.
However, you may be not able to choose two chesses holding the restriction sometimes. So you can also choose exactly one chess x arbitrarily and remove it with cost wx. Moreover, you can do this operation in any situation as long as there is at least one chess on chessboard.
Now you want to remove all the chesses with the minimum total cost. Print the mimimum cost in one line.

The first line contains one positive integers n (1 ≤ n ≤ 12), denoting the size of the chessboard.
Next n lines each contains a string of length n containing only “ . ”, “W” or “B”, denoting the initial chessboard, where cell (i, j) is blank if the j-th character in i-th string is “ . ”, while “W” represents a white chess and “B” represents a black chess.
Next n lines each contains n non-negative integers wi,j (0 ≤ wi,j ≤ 106), denoting the cost values, where the j-th number in i-th line represents the cost value of the chess positioned at (i, j).
It is guaranteed that wi,j is positive if and only if there exists a chess at (i, j).

Output a single line containing a non-negative integer, denoting the mimimum cost.

4
WBB.
BWBW
WBWW
BBBW
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 1

3

642ccpcQHD