Maximize Bus Passengers in Byte City

Byte City is laid out in a regular grid of intersections. The city's north-south streets (NS-streets) are numbered from \(1\) to \(n\) starting from the westernmost, and its west-east streets (WE-streets) are numbered from \(1\) to \(m\) starting from the southernmost. Each intersection is denoted by \((i,j)\) for \(1 \le i \le n\) and \(1 \le j \le m\).

A bus route starts at \((1,1)\) and ends at \((n,m)\). The bus may only travel east (i.e. increasing the \(i\) coordinate) or north (i.e. increasing the \(j\) coordinate). At some intersections, passengers are waiting to board the bus. The driver wants to choose a route that collects the maximum number of passengers. Assume the bus has unlimited capacity.

Your task is to compute the maximum number of passengers the bus can pick up while traveling from \((1,1)\) to \((n,m)\) under the movement restrictions.

Note: The optimal strategy is to use dynamic programming where the recurrence can be written as:

[ dp(i,j)=value(i,j)+\max(,dp(i-1,j),,dp(i,j-1),), \quad \text{for } i>1 \text{ and } j>1, ]

with appropriate boundary conditions.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) denoting the number of NS-streets and WE-streets, respectively.

Then follow \(n\) lines each containing \(m\) space-separated non-negative integers. The \(j\)-th number in the \(i\)-th line represents the number of passengers waiting at the intersection \((i,j)\).

outputFormat

Output a single integer: the maximum number of passengers the bus can pick up along the route from \((1,1)\) to \((n,m)\).

sample

3 3
1 2 3
4 5 6
7 8 9

29