Maximum Path Sum in a Grid

Given a 2D grid of non-negative integers, find the maximum path sum from the top-left to the bottom-right corner. At each step, you can move only right or down. The goal is to maximize the sum of the values along the chosen path, including both the starting and ending cells.

The problem can be solved using dynamic programming. Suppose you are given a grid such as:

[ \begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{bmatrix} ]

The maximum path sum for the above grid is 29.

inputFormat

The first line of input contains two integers R and C representing the number of rows and columns of the grid, respectively.

The next R lines each contain C integers separated by spaces, representing the grid.

outputFormat

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

## sample

3 3
1 2 3
4 5 6
7 8 9

29

</p>