시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB86571.429%

문제

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, there are N +1 lines, each of which contains M nonnegative integers: these numbers 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.

제한

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

서브태스크

번호배점제한
130

The number of villages does not exceed 10, and N, M ≤ 40.

230

N, M ≤ 40.

340

No further constraints.

예제 입력 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

힌트

The situations are depicted below together with possible optimum walls. In both cases, the wall is shown as a bold line and squares with villages are colored.

채점 및 기타 정보

  • 예제는 채점하지 않는다.