Maximum People Path

You are given a 2D grid of non-negative integers where each cell represents the number of people at that location. Starting from the top-left cell and ending at the bottom-right cell, you are allowed to move either right, down, or diagonally down-right. Your task is to determine the maximum sum of people that can be accumulated along a path that follows these movements.

The problem can be formulated using dynamic programming. Let \(dp_{i,j}\) denote the maximum number of people that can be collected from the start to cell \((i,j)\). The recurrence relation is given by:

[ dp_{i,j} = grid_{i,j} + \max{ dp_{i-1,j},; dp_{i,j-1},; dp_{i-1,j-1} } ]

with the boundary conditions being that you can only move right in the first row and only move down in the first column.

Note: The input will be provided via stdin and the output is expected via stdout.

inputFormat

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

This is followed by \(m\) lines, each containing \(n\) space-separated integers representing the grid.

Example:

3 3
1 2 3
4 5 6
7 8 9

outputFormat

Output a single integer representing the maximum sum of people along a valid path from the top-left corner to the bottom-right corner.

Example:

29

## sample

3 3
1 2 3
4 5 6
7 8 9

29