마리오와 평행 세계

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

요약

양의 정수가 적힌 격자에서 오른쪽과 아래로만 이동하는 최대 합 경로를 구합니다. 한 칸을 막아 그 최댓값을 가장 작게 만들 때의 값을 출력합니다.

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

문제

어느 날 마리오와 루이지가 평행 세계로 이동했다. 이 세계는 $n$ 행 $m$ 열의 행렬이며, 각 칸에는 양의 정수가 적혀 있다. 마리오의 목표는 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 가면서 최대한 많은 점수를 얻는 것이다. 마리오는 한 번의 이동으로 현재 칸의 오른쪽 또는 아래쪽 인접한 칸으로 이동할 수 있다(그런 칸이 존재하는 경우에 한한다).

마리오가 얻는 점수는 경로에서 방문한 칸에 적힌 수의 합이다. 루이지는 최근 마리오와 사이가 틀어져서 그를 방해하려 한다. 루이지는 왼쪽 위 모서리와 오른쪽 아래 모서리가 아닌 칸 하나를 차지할 수 있다. 그 칸은 마리오가 지날 수 없게 된다. 루이지는 새 조건에서 마리오가 최적의 경로를 택하더라도 얻는 점수가 최대한 적어지도록 칸을 고른다.

루이지가 마리오의 결과를 최대한 나쁘게 만들도록 행동할 때, 마리오가 최적의 경로로 얻는 점수를 구하라. 루이지가 어느 칸을 차지하더라도 마리오는 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 갈 수 있다고 보장된다.

입력

첫 줄에 두 정수 $n$ , $m$ 이 주어진다. 각각 필드의 길이와 너비이다 ( $2 \le n,m \le 1500$ ).

다음 $n$ 개의 줄에는 각각 $m$ 개의 정수가 주어진다. $i$ 번째 줄의 $j$ 번째 수 $a_{i,j}$ 는 그 칸에 적힌 수이다 ( $1 \le a_{i,j} \le 10^9$ ).

출력

루이지도 최적으로 행동할 때, 마리오가 최적의 경로로 얻는 점수를 한 줄에 출력한다.

힌트

문제 조건의 첫 번째 테스트에서는 루이지가 2번째 행의 3번째 칸을 차지할 때가 최적이다. 이때 마리오는 최대 17점까지만 얻을 수 있다.

예제1

예제 1
입력
```
4 4
1 2 3 4
2 1 3 1
3 2 3 5
1 3 4 1
```
예상 출력
```
17
```