The Wall

The island of Rectos is always threatened by floods and pirates. The king of Rectos wants to protect every village on the island with a single huge wall.

Rectos is a rectangle. The architect who designs the wall models the island as a grid of squares. Each village lies inside one square, and the capital village lies in the very north-west, that is, in the upper left square.

The wall must make it impossible to reach any village from the outside, meaning the area outside the grid, without crossing the wall.

The architect builds the wall along grid lines only. He puts the first wall segment on one of the two grid line segments that start in the upper left corner. Each later wall segment is linked to the previous one: it is built on a grid line segment that starts where the previous one ends. He keeps going until he reaches the upper left corner again. This may put several wall segments on the same grid line segment. The wall is therefore one closed path of grid line segments.

Because of the terrain, every grid line segment has its own cost for one wall segment built on it. The total cost of the wall is the sum of the costs of all wall segments built. If $t$ wall segments are built on the same grid line segment, the cost of that grid line segment is counted $t$ times.

You are given the location of the villages and the building cost of every grid line segment. Compute the minimum cost of building the wall.

The first line contains two integers $N$ and $M$, the number of rows and the number of columns of the grid.

The next $N$ lines describe the rows of the grid from top to bottom. Each line contains $M$ integers that are 0 or 1, listed from left to right: 0 is an empty square and 1 is a square that holds a village. The first integer of the first of these lines is always 1.

The next $N$ lines contain $M + 1$ integers each. The $j$-th number of the $i$-th line is the cost of one wall segment on the $j$-th vertical grid line segment of row $i$, counted from the left.

The next $N + 1$ lines contain $M$ integers each. The $j$-th number of the $i$-th line is the cost of one wall segment on the $j$-th segment of the $i$-th horizontal grid line, counted from the top and from the left.

Print the minimum cost of building the wall.

• $1 \le N, M \le 400$
• every cost $v$ is an integer with $1 \le v \le 10^9$
• the answer can exceed the range of a 32-bit integer

The picture below shows an optimum wall for each of the two example inputs. The wall is drawn as a bold line and the squares with villages are colored.