햄스터

시간 제한2초메모리 제한1024 MB

요약

N행 M열 격자에서 북서쪽 모서리부터 남동쪽 모서리까지 같은 칸을 두 번 지나지 않는 경로의 애벌레 합 최댓값을 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 행렬, 구현
정답자: 아직 제출이 없습니다

문제

햄스터는 직사각형 모양의 우리에서 살고 있습니다. 바닥은 같은 크기의 정사각형 칸으로 나뉘어 격자를 이루고, 각 칸에는 애벌레가 여러 마리 있습니다.

햄스터는 북서쪽 모서리에서 출발합니다. 방문한 칸에서는 애벌레를 그릇에 담고, 그 칸에 덫을 놓은 뒤, 지금 떠나는 칸과 변을 공유하는 옆 칸으로 이동합니다. 이미 방문한 칸으로는 돌아갈 수 없습니다. 자신이 놓은 덫에 걸리기 때문입니다. 여정은 남동쪽 모서리에서 끝납니다.

각 칸의 애벌레 수가 주어질 때, 어떤 덫에도 걸리지 않고 모을 수 있는 애벌레의 최대 개수를 구하세요.

입력

첫 줄에 행의 수 $N$ 과 열의 수 $M$ 이 주어집니다 ( $2 \le N, M \le 1000$ ). 이어서 $N$ 개의 줄이 주어지며, 각 줄에는 $M$ 개의 정수가 있고 각 칸의 애벌레 수를 나타냅니다. 한 줄이 격자의 한 행에 해당합니다. 첫 번째 줄의 첫 번째 수가 북서쪽 모서리이고, 마지막 줄의 마지막 수가 남동쪽 모서리입니다.

각 칸의 애벌레 수는 $0$ 이상 $1000$ 이하입니다.

출력

모을 수 있는 애벌레 수의 최댓값을 한 개의 수로 출력하세요.

예제2

예제 1
입력
```
2 2
1 2
3 4
```
예상 출력
```
8
```
예제 2
입력
```
3 4
2 2 4 0
1 3 1 0
2 5 3 1
```
예상 출력
```
24
```