Maximizing the Scenic Route Score

A tourist city has a grid layout. The east‐west streets, called "scenic roads", each have a score assigned by a tourist according to how much they like the scenery. The scores are integers in the range \(-100\) to \(+100\) (with \(-100 \leq s \leq 100\)), and at least one scenic road has a non‐negative score.

The east–west scenic roads are one-way: you can only travel from west to east along them. The north–south streets, called "laneways", have no associated scores and allow movement in both directions. A tourist can start at any intersection and finish at any intersection. Whenever the tourist travels a scenic road (east–west edge), the score of that road is added to the total. Moving along a laneway (north–south edge) does not change the score.

Your task is to help the tourist choose a route with the maximum possible sum of scenic road scores.

Observation: Since the laneways allow free vertical movement, the tourist can always reposition to any row at the same column. Thus, at each column, the tourist’s decision is simply which east–west road (in one of the rows) to take next. Effectively, if the grid has R rows and C columns of intersections, then each row provides \(C-1\) east–west roads. For each column j (1 ≤ j ≤ C-1), let \(a_j = \max_{1 \le i \le R}\{s_{i,j}\}\), where \(s_{i,j}\) is the score of the scenic road in row i between column j and j+1. The problem then reduces to finding the maximum contiguous subarray sum of the sequence \(a_1, a_2, \dots, a_{C-1}\). If all choices would lead to a negative sum, the tourist may choose a route with no east–west moves resulting in a score of 0.

inputFormat

The input begins with a line containing two integers R and C, where R is the number of rows (scenic road rows) and C is the number of columns of intersections. It is followed by R lines. Each of these lines contains C-1 integers; the j-th integer in the i-th line represents the score \(s_{i,j}\) of the east–west scenic road in row i between intersection j and j+1.

outputFormat

Output a single integer, the maximum total scenic road score that can be achieved by an optimal route.

sample

3 4
1 2 3
-1 2 -1
0 0 5

11