G. Game on Chessboard
time limit per test
1.0 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a chessboard of size $$$n\times n$$$. The rows are numbered $$$1, 2, \cdots, n$$$ from top to bottom while the columns are numbered $$$1, 2, \cdots, 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 $$$|w_u - w_v|$$$. 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 $$$(x_1, y_1)$$$ that $$$x_1 \ge x$$$ and $$$y_1 \le 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 $$$w_x$$$. 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.

Input

The first line contains one positive integers $$$n~(1\le n \le 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 $$$w_{i,j}~(0\le w_{i,j} \le 10^6)$$$, 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 $$$w_{i,j}$$$ is positive if and only if there exists a chess at $$$(i,j)$$$.

Output

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

Example
Input
4
WBB.
BWBW
WBWW
BBBW
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 1
Output
3