33997번 - 광부가 될 수 있다면

문제

슈카고등학교 1학년 키타는 슈카고등학교 지하에 광물이 매장되어 있다는 정보를 입수했다. 키타는 이를 듣고 광질을 하여 부자가 되려고 한다. 하지만 슈카고등학교 지하는 매우 위험하기 때문에 길을 잘못 들면 오히려 손해를 볼 수도 있다.

지하는 $N$층 $M$열, $N \times M$크기의 직사각형 모양으로 이루어져 있다. 키타는 같은 층에서 왼쪽, 오른쪽으로 움직일 수 있고, 같은 열의 바로 아래층으로 내려갈 수도 있다. 좌우로는 자유롭게 움직일 수 있지만, 한 번 내려간 뒤에 다시 올라갈 수는 없다. 아직 방문하지 않은 칸에 처음 도착하면 그 칸의 가치만큼 돈을 얻거나 잃는다. 이미 방문한 칸을 다시 지나가는 것은 가능하지만 돈을 추가로 얻거나 잃지는 않는다.

키타는 지하 1층의 원하는 열에서 광질을 시작해 최대한 많은 돈을 벌고, 비상계단을 통해 탈출할 계획을 세웠다. 비상계단은 지하 $N$층에 있기 때문에 반드시 지하 $N$층까지 내려가야 하며, 다른 층에서는 그만둘 수 없다. 비상계단은 모든 열에 있기 때문에 지하 $N$층의 어느 열에서든 광질을 끝낼 수 있다. 키타가 부자가 될 수 있도록 벌 수 있는 돈의 최댓값을 구해주자!

입력

첫째 줄에 $N,ドル $M$이 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 1,000円)$

이후 $N$개의 줄에 걸쳐 정수 $M$개가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 수는 $i$번째 층 $j$번째 열의 가치이다. 이 수의 절댓값은 10ドル^9$ 이하이다.

출력

첫째 줄에 벌 수 있는 돈의 최댓값을 출력한다. 답이 음수가 될 수 있음에 유의한다.

제한

힌트