Comet OJ

C1716 [CEOI2014Day2] The Wall

内存限制：1024 MB 时间限制：2000 ms

题目描述

The island of Rectos is always threatened by floods and pirates. Therefore, the king of Rectos wants to protect all villages on his island by a single huge wall.

Rectos has rectangular shape. So, the architect of the wall models the island as a grid of squares. Each village is located within one of the squares; the capital village is located in the very north-west, i.e. within the upper left square.

The wall must be built in such a way that from the outside (i.e., from the area outside the grid) it is impossible to reach any village without crossing the wall.

The architect plans to build the wall along grid lines only, in the following way: He puts the first wall segment on one of the two grid line segments that start in the upper left corner.

Then, the next wall segment is always linked to the previous one, i.e. built on an adjacent grid line segment (that starts where the previous one ends). The architect continues this way, until the upper left corner is reached again. This procedure may cause that more than one wall segments are put on the same grid line segment. That is, the wall is built along a contiguous closed path of grid line segments.

Due to topography, for every grid line segment there is a certain cost of building a segment of the wall there. The total cost of building the wall is given by the sum of the costs for all segments of the wall. If $t$ wall segments are built on the same grid line segment, the cost of this grid line segment are counted $t$ times.

The king wants to spend as little money as possible for building the wall. Help the king and write a program that, given the location of villages on the island and the building cost for all grid line segments, computes the minimum cost of building the wall.

输入格式

The first line consists of two integers $N$ and $M$, the number of rows and columns of the grid, respectively. The following $N$ lines describe the rows of the grid. Each of these lines contains $M$ integers, either $0$ or $1$: $0$ represents an empty square, while $1$ indicates the presence of a village in this square. The first integer in the first of these lines is $1$.

Afterwards, there are $N$ more lines, each of which contains $M + 1$ nonnegative integers: these numbers specify the cost of building a wall segment along the corresponding vertical grid line segment.

Finally,thereare $N+1$ lines, each of which contains $M$ nonnegative integers: thesenumbers specify the cost of building a wall segment along the corresponding horizontal grid line segment.

输出

The only line of the output should contain a single integer: the minimum cost of building the wall.

样例

样例输入 1

3 3
1 0 0
1 0 0
0 0 1
1 4 9 4
1 6 6 6
1 2 2 9
1 1 1
4 4 4
2 4 2
6 6 6

样例输出 1

38

样例输入 2

3 3
1 0 1
0 0 0
0 1 0
2 1 1 3
5 6 1 1
2 1 1 3
2 1 1
3 4 1
4 1 1
5 1 2

样例输出 2

22

提示

Constraints

It holds that $1 ≤ N,M ≤ 400$, and $1 ≤ v ≤ 10^9$ for all cost values $v$. However, you might need long long to store the result!

Subtask 1 (30points). The number of villages does not exceed $10$, and $N,M ≤40$.

Subtask 2 (30points). $N,M ≤40$.

Subtask 3 (40points). No further constraints.