탐험가 루나는 \(R \times C\) 격자 지도의 왼쪽 위 칸 \((1, 1)\)에서 출발해 오른쪽 아래 칸 \((R, C)\)로 이동하려 한다. 각 칸에는 황금이 \(g_{r,c}\)개 묻혀 있다.

루나는 매 이동마다 오른쪽 또는 아래쪽으로 한 칸씩 이동할 수 있다. 방문하는 모든 칸의 황금을 수집한다.

루나는 모험 중 단 한 번, 대각선 지름길을 쓸 수 있다: 현재 칸에서 오른쪽 아래 대각선 방향으로 한 칸 이동한다 (즉, \((r, c) \to (r{+}1, c{+}1)\)).

수집할 수 있는 황금의 최대 개수를 구하여라.

• \(1 \le R, C \le 500\)
• \(-10^6 \le g_{r,c} \le 10^6\)

첫째 줄에 행의 수 \(R\)과 열의 수 \(C\)가 공백으로 구분되어 주어진다.

다음 \(R\)개의 줄에 각 행의 황금 수 \(g_{r,1}, g_{r,2}, \dots, g_{r,C}\)가 공백으로 구분되어 주어진다.

수집할 수 있는 황금의 최대 개수를 출력한다.

riseoj 작성

출처 Original