실버런

실버런(Silver Run)은 2차원 맵에서 캐릭터를 조종해서 최대한 많은 실버를 모으는 것이 목적인 모바일 게임이다.

실버런의 맵에는 실버 주머니들이 상하좌우로 일정한 간격을 두고 N행 M열의 직사각형 모양으로 배치되어 있으며, 각 주머니에는 정해진 개수만큼의 실버가 들어 있다.
편의상 상하좌우로 이웃한 실버 주머니 사이의 간격을 한 칸이라고 표현하며, 가장 왼쪽 위 주머니로부터 왼쪽으로 한 칸, 위로 한 칸 떨어진 위치로부터 아래로 x칸, 오른쪽으로 y칸 떨어진 위치를 (x, y)라고 표현한다. 즉 가장 왼쪽 위 주머니의 위치는 (1, 1), 가장 오른쪽 아래 주머니의 위치는 (N, M)이다.

게임이 시작되면 실버 주머니들은 1초당 한 칸의 일정한 속도로 왼쪽으로 움직이며, 유저는 캐릭터를 이동시키며 캐릭터와 부딪히는 실버 주머니에 든 실버를 획득하게 된다.
캐릭터와 주머니의 크기는 충분히 작아서, 실버를 획득하기 위해서는 캐릭터와 주머니의 위치가 정확히 일치해야 한다.

이 게임에서 가장 좋은 캐릭터는 16silver라는 캐릭터이다. 16silver는 임의의 위치에서 출발할 수 있으며(정수 좌표가 아니어도 된다!), 1초당 한 칸의 일정한 속도로 위, 아래 또는 오른쪽으로 이동할 수 있다. 그러나 제자리에 멈춰 있을 수는 없으며, 1초 단위로만 이동 명령을 내릴 수 있다. 예를 들어 "위로 2.5초 동안 이동"과 같은 명령은 내릴 수 없다.

맵이 주어질 때, 16silver 캐릭터를 이용해 모을 수 있는 실버의 최대 수량을 구하는 프로그램을 작성해 보자.

첫 번째 줄에 맵에 있는 실버 주머니들이 이루는 직사각형의 행과 열 수를 나타내는 정수 N, M(1 ≤ N, M ≤ 1,000)이 공백을 사이에 두고 주어진다.

다음 N개의 줄에 걸쳐 각 줄에 M개의 정수가 주어진다. i번째 줄의 j번째 정수는 (i, j) 위치에 있는 실버 주머니에 들어 있는 실버의 양이며, 입력되는 모든 정수는 0 이상 100,000 이하이다.

첫 번째 줄에 16silver 캐릭터로 모을 수 있는 실버의 최대 수량을 출력한다.

첫 번째 예제의 경우, 아래 그림과 같이 (3, 0) 위치에서 시작하여 위-아래-오른쪽-위 순서대로 1초씩 움직이면 99+99+97+98+96=489개의 실버를 얻을 수 있다.