Informatica Online Judge

  격류지대 (Tiny) [1948 / 079C]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 9   Total Tried : 13


The Champion of this Problem (C++) : gs17100 - 0ms / 907byte
My Best Submission (C++) : N/A

[koistudy.net (34th 김태영)]
Writer ID : [gs16022]

Background

온라인 게임 메이플스토리의 격류지대라는 맵은 N*M 형태로 이루어진 격자 모양이며, 왼쪽 아래를 (0, 0) 그리고 오른쪽 위를 (M-1, N-1)으로 정의한다. 이 N*M 맵에는 코어 젬스톤이 라는 아이템이 위치 되어 있다. 코어 젬스톤은 굉장히 비싸기 때문에 태영이는 이 격류지대라는 맵에서 코어 젬스톤을 최대한 많이 먹고 싶다.

태영이가 격류지대 맵에 도착하면 (0, 0) 에 위치한다. 격류지대는 왼쪽에서 오른쪽으로 흐르는 강 형태이기 때문에, 1초가 지나면 태영이의 x좌표는 1이 증가하며 태영이가 오른쪽에서 왼쪽으로 갈 수 있는 방법은 없다. 1초동안 태영이는 X만큼 y좌표를 이동할 수 있다. 예를 들자면 X = 2 라고 가정하고 태영이가 (1, 4) 에 있었다면, 1초 후의 태영이는 (2, 2) ~ (2, 6) 사이에 모든 점으로 이동할 수 있다.

태영이가 (0, 0)에서 출발하여 x좌표가 M-1으로 가는 동안 최대한 많은 코어 젬스톤을 먹으려고 한다. 태영이를 도와주자.

Input

첫 번째 줄에 N, M, X 가 주어진다. - (N, M) 맵이고, 1초동안 X만큼 y좌표를 이동할 수 있다는 뜻
두 번째 줄부터 N+1 번째 줄에는 N*M 맵에 위치한 코어 젬스톤 수가 입력된다.
( 1 <= 한 칸의 코어 젬스톤의 개수 <= 1000 )

격류지대 Tiny : (1 <= N, M, X <= 500)

Output

태영이가 위 조건을 만족하며 가장 많이 먹을 수 있는 코어 젬스톤의 개수를 출력하여라.

IO Example

입력 예제

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

출력 예제
17

예제 설명
(0, 0) -> (1, 1) -> (2, 2) -> (3, 2) 로 이동하면 4 + 4 + 5 + 4 = 17개의 젬스톤을 먹을 수 있다.
입력 조건

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