프로그램 명: martian_mining
제한시간: 1 초
//번역 + 채점 데이터 자르는 중..........

NASA 우주 세터 Houston 은 San Antonio ,Texas(올 ACM Final 장소)에서 200 마일 안쪽에 있다. 우주 탐사에서 큰 도약을 위한 Mission Seven Dwarfs 를 위해 우주비행사들이 훈련을 받는 곳이다. 화성 Odyssey 프로그램은 화성의 표면에 yeyenum 과 blogginum 이 매우 풍부하다는 것을 밝혀내었다. 이 광물들은 혁신적인 새로운 의약재료로 중요한 물질이지만 지금에서는 거의 없다. Misson Seven Dwarfs 의 목표는 화성에 있는 이 광물들을 지구로 가져오는 것이다.

Mars Odyssy 위성은 광물이 풍부한 화성 표면의 직사각형의 면적을 알아내었다. 이 면적은 n*m 의 행렬의 셀로 나눈다. 행은 동에서 서로 , 열은 북에서 남으로 간다. 위성은 yeyenum 과 bloggium 의 양을 결정했다. 우주 비행사는 yeyenum 정제소를 직사각형의 서쪽에 지었고 북쪽에는 blogginum 공장을 지었다. 당신의 일은 가장 많은 양의 미네랄을 가져올수 있는 컨베이어 시스템을 설계하는 것이다.

There are two types of conveyor belts: the first moves minerals from east to west, the second moves minerals from south to north. In each cell you can build either type of conveyor belt, but you cannot build both of them in the same cell. If two conveyor belts of the same type are next to each other, then they can be connected. For example, the bloggium mined at a cell can be transported to the bloggium refinement factory via a series of south-north conveyor belts.

두 가지 타입의 컨베이어 벨트가 있다. 처음 것은 미네랄을 동에서 서로 옮긴다. 다음 것은 남에서 북으로 옮긴다. 각 셀에서 당신은

The minerals are very unstable, thus they have to be brought to the factories on a straight path without any turns. This means that if there is a south-north conveyor belt in a cell, but the cell north of it contains an east-west conveyor belt, then any mineral transported on the south-north conveyor beltwill be lost. The minerals mined in a particular cell have to be put on a conveyor belt immediately, in the same cell (thus they cannot start the transportation in an adjacent cell). Furthermore, any bloggium transported to the yeyenum refinement factory will be lost, and vice versa. 이 미네랄들은 매우 불안정하여 꺽임이 없이 직선코스로 공장에 가져와야 한다.

Your program has to design a conveyor belt system that maximizes the total amount of minerals mined,i.e., the sum of the amount of yeyenum transported to the yeyenum refinery and the amount of bloggium transported to the bloggium refinery.

입력

The input contains several blocks of test cases. Each case begins with a line containing two integers: the number 1 ≤ n ≤ 500 of rows, and the number 1 ≤ m ≤ 500 of columns. The next n lines describe the amount of yeyenum that can be found in the cells. Each of these n lines contains m integers. The first line corresponds to the northernmost row; the first integer of each line corresponds to the westernmost cell of the row. The integers are between 0 and 1000. The next n lines describe in a similar fashion theamount of bloggium found in the cells. The input is terminated by a block with n = m = 0.

출력

For each test case, you have to output a single integer on a separate line: the maximum amount of mineralsthat can be mined.

입출력 예

입력

4 4
0 0 10 9
1 3 10 0
4 2 1 3 
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
0 0

출력

98

Hint

Huge input file, 'scanf' recommended to avoid TLE. 
출처: Central Europe 2005
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]