C. Black-White Cubic Lattice
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a cubic lattice of size $$$N \times M\times L$$$ such that each lattice point $$$(i,j,k)$$$ is either white or black. The coordinates of the lattice point are all positive integers. Let the cost of flipping the color of lattice point $$$(i,j,k)$$$ be $$$a_{i,j,k}$$$. Find the minimum cost to flip the colors of lattice points such that the bottom left corner $$$(1,1,1)$$$ is black, the top right corner $$$(N,M,L)$$$ is white, and any two different lattice points $$$(i_1, j_1, k_1)$$$ and $$$(i_2,j_2,k_2)$$$ satisfy at least one of the following conditions.

  • $$$i_1 \gt i_2$$$
  • $$$j_1 \gt j_2$$$
  • $$$k_1 \gt k_2$$$
  • $$$(i_1, j_1, k_1)$$$ is black.
  • $$$(i_2, j_2, k_2)$$$ is white.
Input

The first line includes three integers $$$N, M, L$$$ ($$$1\le N, M, L\le 5\times 10^3$$$, $$$2 \leq N \times M \times L \leq 5\times 10^3$$$), denoting the size of the lattice. Each of the next $$$L \times N$$$ lines contains a string of length $$$M$$$ that only consists of B and W. The initial color of lattice point $$$(i,j,k)$$$ is the $$$j$$$-th character of the $$$(k-1) \times N + i$$$ line. If the character is B, it means the color of the lattice point is black, otherwise it is white. Each of the next $$$L \times N$$$ lines contains $$$M$$$ non-negative integers not greater than $$$10^5$$$. The cost of flipping the color of lattice point $$$(i,j,k)$$$ is the $$$j$$$-th integer of the $$$(k-1) \times N + i$$$ line.

Output

Output the minimum cost.

Example
Input
2 2 2
WW
WW
BB
BB
1 1
1 1
2 2
2 2
Output
5