계산 로봇

$ M $개의 행(가로줄)과 $ N $개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다.

각 행에는 위에서부터 아래로 $ 1 $부터 $ M $까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 $ 1 $부터 $ N $까지의 번호가 붙어 있다. 이를 통해 격자 칸의 위치를 (행 번호, 열 번호)의 좌표로 표시할 수 있다.

각 로봇은 하나 이상의 입력 값, 하나의 저장 값, 하나의 출력 값을 가진다.

로봇들은 제일 왼쪽 열의 로봇들부터 열 번호 순서대로 동작한다. 같은 열에 있는 로봇들은 동시에 동작한다.

로봇들의 동작은 다음과 같다. (표현 $ |A| $는 정수 $ A $의 절댓값을 의미한다. 즉, $ A\ge 0 $인 경우 $ |A| = A $, $ A < 0 $인 경우 $ |A| = -A $.)

• 제일 왼쪽 열에 있는 로봇의 입력 값은 $ 0 $ 하나로 정한다.
• 좌표 $ (i,j) $의 로봇의 입력 값은 $ |i - a| \le j - b $, $ b < j $인 모든 좌표 $ (a,b) $에 있는 로봇들의 출력 값들이다. (아래 그림에서 별로 표시된 칸의 로봇의 입력 값들은 왼쪽 회색 칸들의 로봇들의 출력 값들이다.)

• 각 로봇은 자신의 입력 값들 중 최댓값을 자신의 저장 값으로 한다.
• 각 로봇은 자신의 저장 값에 자신의 가중치 $ D_{i,j} $를 더한 값을 자신의 출력 값으로 한다.

로봇들의 가중치를 입력받아 로봇들의 저장 값 중 최댓값(가장 큰 값)을 계산하는 프로그램을 작성하라.

• $ 1 \le M \le 2\,000 $
• $ 1 \le N \le 2\,000 $.
• 모든 $ i $, $ j $ ($ 1 \le i \le M $, $ 1 \le j \le N $)에 대해, $ 1 \le D_{i,j} \le 9 $.

1. (3점) $ N=1 $.
2. (8점) $ N=2 $.
3. (9점) $ M=1 $.
4. (21점) $ M \le 100 $, $ N \le 100 $.
5. (59점) 추가 제약 조건 없음.

첫 번째 줄에 두 정수 $ M $과 $ N $이 공백 하나를 사이로 두고 주어진다.

다음 $ M $개의 줄에는 로봇들의 가중치들이 행 순서대로 주어진다. 각각의 줄은 한 행에 해당하며 $ N $개의 숫자(한 자리 수)로 이루어진 문자열이 주어진다. 각 숫자는 격자 칸의 로봇의 가중치를 의미한다. 즉, 여기서 $ i $번째 줄의 $ j $번째 문자가 $ D_{i,j} $이다.

첫 번째 줄에 로봇들의 저장 값 중 최댓값을 출력한다.