Informatica Online Judge

  등산 [1322 / 052A]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 12   Total Tried : 16


The Champion of this Problem (C++) : gs15120 - 117ms / 1781byte
My Best Submission (C++) : N/A

[koistudy.net (32nd 최재현)]

Background

재현이는 등산을 가려고 한다.

재현이는 등산을 하고 올라가서 경치를 구경하는 것을 좋아하기 때문에, 경치가 가장 멋있는 등산 경로를 찾으려고 한다.

산은 W*H의 직사각형 격자로 이루어져 있으며, 각각에 대하여 그 장소의 선호도 X와 높이 Y가 주어진다.

그가 등산하는 동안 보는 멋있음은 그가 등산하는 경로와 하산하는 경로에 있는 모든 장소의 선호도의 합이다.

(물론 올라갈 때의 경로와 내려갈 때의 경로가 같아도 상관이 없다.)

재현이는 올라갈 때에는 무조건 지금 있는 곳 보다 높은 곳으로 올라가고, 내려갈 때에는 무조건 지금 있는 곳 보다 낮은 곳으로 올라간다.

재현이는 경치가 가장 멋있는 경로를 찾으려고 하지만 정보 실력이 좋지 않기 때문에 구할 수 없다고 한다. 재현이를 도와주자.

※내려올 때 올라올 때 이미 지나간 경로여도 그 곳에 선호도가 멋있음에 추가된다.

즉, 같은 곳을 2번 갔다고 해서 선호도가 한 번만 추가 되는 것이 아니라 2번 추가된다는 것이다.

Input

첫째 줄에 산의 가로 길이인 W와 세로 길이인 H가 주어진다. (1<=W<=1,000,1<=H<=1000)

그 다음 H줄에는 한 줄에 W개의 높이 Y가 주어진다. (1<=Y<=10,000)

그 다음 H줄에는 한 줄에 W개의 선호도 X가 주어진다. (1<=X<=10,000)

Output

첫째 줄에 재현이가 볼 수 있는 경치의 멋있음의 최댓값을 출력한다.

IO Example

입력
3 3
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9

출력
49

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]