Taco Maximum Path Sum

You are given a 2D grid of non-negative integers. Your task is to calculate the maximum sum a robot can collect while moving from the top-left cell to the bottom-right cell. The robot can only move either right or down at any point in time.

The problem can be expressed mathematically as finding the maximum path sum:

$$\text{dp}[i][j] = \max(\text{dp}[i-1][j],\, \text{dp}[i][j-1]) + grid[i][j] $$

where grid[i][j] represents the value of the cell at row i and column j and dp[i][j] represents the maximum sum to reach that cell.

Input: The first line contains two integers R and C, representing the number of rows and columns in the grid. The next R lines each contain C space-separated integers representing the grid.

Output: Output a single integer representing the maximum sum that can be collected.

inputFormat

The first line of input contains two integers R and C which denote the number of rows and columns in the grid respectively. Each of the next R lines contains C space-separated non-negative integers representing the grid.

outputFormat

Output a single integer which is the maximum sum obtainable by following a valid path from the top-left to the bottom-right of the grid.

## sample

3 3
1 3 1
1 5 1
4 2 1

12