1579번 - 보물 찾기

세준이가 좋아하는 게임의 최신 버전이 나왔다. 이 게임의 각 레벨에서 세준이는 보물을 찾아서 점수를 올려야 한다. 간단하게 보물이 있는 위치로 이동하게 되면, 그 곳에 있는 보물을 자동으로 획득하게 된다.

세준이는 게임을 쉽게 하고, 점수를 많이 얻기 위해 이미 현재 레벨의 지도를 가지고 있다. 이 지도는 세로 크기가 N이고, 가로 크기가 M이다. 또, 한 칸에 하나씩 숫자를 나타내고 있다. 여기서 나타내는 수는 그 위치에서 보물의 양이다. 또, 항상 가장 왼쪽 위의 칸에 있는 보물의 양은 0이다.

세준이는 게임을 가장 왼쪽 위의 칸에서 시작한다. 이 게임은 총 세 개의 스테이지로 구성되는데, 다음과 같은 규칙을 따라서 지나야 한다.

1. 첫 번째 스테이지에선 아래와 오른쪽으로만 이동할 수 있다. 이때, 목적지는 반드시 가장 오른쪽 아래이어야 한다.
2. 두 번째 스테이지에서는 가장 왼쪽 위로 올라가야 한다. 이때는 위와 왼쪽으로만 이동할 수 있다.
3. 세 번째 스테이지에서는 첫 번째 스테이지와 마찬가지로 가장 아래와 오른쪽으로만 이동할 수 있고, 목적지는 반드시 가장 오른쪽 아래이어야 한다.

어떤 칸을 한 번 지나갔으면, 그 때 보물은 다 가지고 와야 한다. 만약, 그 칸을 두 번째 지나갔을 때는, 보물을 얻지 못한다.

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, 각 칸에 주어지는 수는 1,000보다 작거나 같은 음이 아닌 정수이다.

첫째 줄에 정답을 출력한다. 정답은 2147483647보다 작거나 같다.