Max Sum Path in a Grid

You are given an R × C grid of integers. Starting from the top-left cell (i.e. cell at row 1, column 1), your task is to find a path to the bottom-right cell (i.e. cell at row R, column C) that maximizes the sum of the integers collected along the way.

You can move in one of the following three directions at each step:

• Right: from cell \((i,j)\) to \((i, j+1)\)
• Down: from cell \((i,j)\) to \((i+1, j)\)
• Diagonally Down-Right: from cell \((i,j)\) to \((i+1, j+1)\)

The optimal solution can be computed using dynamic programming. In particular, define a DP array \(dp\) such that:

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

where the indices for \(dp\) are in 0-based format and correspond to grid positions. The answer will be \(dp[R-1][C-1]\).

inputFormat

The input is provided via standard input (stdin) in the following format:

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

outputFormat

Output a single integer to standard output (stdout) which is the maximum sum that can be collected by moving from the top-left to the bottom-right cell following the allowed moves.

## sample

3 3
1 2 3
4 5 6
7 8 9

29