Computing Robots

Each cell of a grid with M rows (horizontal lines) and N columns (vertical lines) contains a robot.

Rows are numbered 1 to M from top to bottom, and columns are numbered 1 to N from left to right. A cell's position is therefore written as the coordinate (row number, column number).

Each robot has one or more input values, one stored value, and one output value.

The robots operate column by column, starting with the robots in the leftmost column. Robots in the same column operate simultaneously.

The robots behave as follows. (Here |A| denotes the absolute value of the integer A. That is, if A ≥ 0 then |A| = A, and if A < 0 then |A| = −A.)

• The input value of a robot in the leftmost column is defined to be the single value 0.
• The input values of the robot at coordinate (i, j) are the output values of the robots at all coordinates (a, b) with |i−a| ≤ j − b and b < j. (In the figure below, the input values of the robot in the cell marked with a star are the output values of the robots in the gray cells to its left.)

• Each robot sets its stored value to the maximum of its input values.
• Each robot sets its output value to its stored value plus its weight Di,j.

Given the weights of the robots, write a program that computes the maximum (largest value) among the robots' stored values.

The first line contains two integers M and N separated by a single space.

The next M lines give the robots' weights in row order. Each line corresponds to one row and contains a string of N digits (each a single digit). Each digit is the weight of the robot in that grid cell. That is, the j-th character of the i-th line is Di,j.

Print the maximum among the robots' stored values on the first line.

• 1 ≤ M ≤ 2 000
• 1 ≤ N ≤ 2 000
• For all i, j (1 ≤ i ≤ M, 1 ≤ j ≤ N), 1 ≤ Di,j ≤ 9.