Maximum Path Sum in a Grid

Given a grid of size n × m containing non-negative integers, your task is to find the maximum sum achievable when moving from the top-left corner to the bottom-right corner. You are only allowed to move either right or down at each step.

The problem can be solved using dynamic programming. Define a DP table \(dp[i][j]\) such that:

\(dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + grid[i][j]\)

with the proper initialization of the first row and first column. Input is provided via standard input (stdin) and output via standard output (stdout).

inputFormat

The input begins with a line containing two space-separated integers n and m (the number of rows and columns, respectively). This is followed by n lines, each containing m space-separated non-negative integers representing the grid values.

outputFormat

Output a single integer — the maximum sum from the top-left corner to the bottom-right corner by moving only right or down.

3 3
1 2 3
4 5 6
7 8 9

29