보물 찾기

세준이는 새 게임의 각 레벨에서 지도를 따라 이동하며 보물을 모은다. 지도의 크기는 세로 N칸, 가로 M칸이고, 각 칸에는 그 칸에 있는 보물의 양이 적혀 있다. 왼쪽 위 칸의 값은 항상 0이다.

세준이는 왼쪽 위 칸에서 시작해 다음 세 단계를 차례로 진행한다.

1. 첫 번째 단계에서는 아래쪽 또는 오른쪽으로만 이동해 오른쪽 아래 칸에 도착해야 한다.
2. 두 번째 단계에서는 위쪽 또는 왼쪽으로만 이동해 다시 왼쪽 위 칸으로 돌아와야 한다.
3. 세 번째 단계에서는 다시 아래쪽 또는 오른쪽으로만 이동해 오른쪽 아래 칸에 도착해야 한다.

어떤 칸을 처음 지날 때 그 칸의 보물을 모두 얻는다. 이미 지난 칸을 다시 지나면 그 칸에서는 더 이상 보물을 얻지 못한다. 세 단계 동안 얻을 수 있는 보물의 최대 총량을 구하라.

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 각 칸의 보물 양을 나타내는 M개의 정수가 주어진다.

N과 M은 50 이하의 자연수이고, 각 칸의 값은 1,000 이하의 음이 아닌 정수이다.

첫째 줄에 얻을 수 있는 보물의 최대 총량을 출력한다. 정답은 2147483647보다 작거나 같다.