Maximizing Scenic Score in a Tourist Grid

In a famous tourist area, the streets form a grid. The east–west roads (called tourism streets) are designated as one‐way roads, meaning you can only travel from west to east. The north–south roads (lined with trees) allow travel in both directions. Each segment between two adjacent intersections on a tourism street is assigned an integer scenic score between \(-100\) and \(100\). In contrast, the tree‐lined roads are not scored. It is guaranteed that not all the scores are negative.

Starting from any intersection on the western boundary (column 1) and ending at any intersection on the eastern boundary (column \(m\)), find a route that adheres to the travel rules and maximizes the total scenic score. Note that you may use the tree–lined roads (vertical moves) freely (with no score change) to reposition yourself in the same column before taking an eastward move along a tourism street.

Explanation: The grid has \(n\) rows and \(m\) columns of intersections. For each row \(i\) (\(1 \le i \le n\)), you are given \(m-1\) integers. The \(j\)-th integer on the \(i\)-th line represents the scenic score for the tourism street segment from the \(j\)-th intersection to the \((j+1)\)-th intersection in that row. Since vertical moves are free and allow you to switch rows arbitrarily within a column, the optimal strategy is to, in each column, choose the segment with the maximum score. Therefore, the maximum scenic score equals the sum over columns \(j=1\) to \(m-1\) of \(\max_{1 \le i \le n}\{a_{i,j}\}\).

inputFormat

The first line contains two integers \(n\) and \(m\) indicating the number of rows and columns of intersections respectively.

Then follow \(n\) lines, each containing \(m-1\) integers. The \(j\)-th integer in the \(i\)-th line represents the scenic score on the tourism street segment between the \(j\)-th and \((j+1)\)-th intersections in the \(i\)-th row.

It is guaranteed that \(-100 \leq a_{i,j} \leq 100\) and not all scores across the grid are negative.

outputFormat

Output a single integer: the maximum total scenic score achievable from the western boundary to the eastern boundary under the given movement restrictions.

sample

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

9