Cho một bàn cờ ~n \times n~. Các hàng được đánh số từ ~1~ tới ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ tới ~n~ từ trái qua phải (Ô ~(1, 1)~ là góc trái trên và ~(n, n)~ là góc phải dưới).
Trên một số ô của bàn cờ có chứa một quân cờ mang màu trắng hoặc đen (số còn lại không chứa gì), quân cờ ở ô ~(i, j)~ có giá trị là ~w_{ij}~.
Nhiệm vụ của bạn là bốc được hết các quân cờ ra khỏi bàn cờ. Tại mỗi bước, bạn có thể chọn một quân cờ trắng ~u~ và một quân cờ đen ~v~ và xóa chúng ra khỏi bàn cờ trong thời gian ~|w_u - w_v|~. Tuy nhiên, một quân cờ ~(x, y)~ chỉ được phép chọn ở thao tác này nếu hiện tại không có quân cờ ~(x_1, y_1)~ nào khác mà ~x_1 \geq x~ và ~y_1 \leq y~.
Ngoài ra, bạn cũng có thể chọn một quân cờ ~u~ bất kỳ trên bàn cờ và đưa nó ra khỏi bàn trong thời gian ~w_u~.
Bạn hãy tính thời gian ngắn nhất có thể để đưa hết cờ ra khỏi bàn.
Input
Dòng đầu chứa một số nguyên dương ~n (1 \leq n \leq 12)~.
~n~ dòng tiếp theo mỗi dòng chứa một xâu gồm ~n~ ký tự ".", "W" hoặc "B" biểu diễn một ô trống, một ô chứa cờ trắng hoặc một ô chứa cờ đen.
~n~ dòng tiếp theo mỗi dòng chứa một dãy ~n~ số nguyên dương. Số nguyên dương thứ ~j~ của dòng thứ ~i~ là giá trị ~w_{ij} (0 \leq w_{ij} \leq 10^{6}).~
Oụtput
In ra một số nguyên duy nhất là thời gian ngắn nhất để chuyể hết các quân cờ ra khỏi bàn.
Sample Input 1
4
WBB.
BWBW
WBWW
BBBW
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 1
Sample Output 1
3
Bình luận