Maximum Path Score in a Grid

You are given a grid of non-negative integers with n rows and m columns. Your task is to determine the maximum score achievable when moving from the top-left corner to the bottom-right corner. From any cell, you may only move either right or down.

The problem can be solved using dynamic programming. The recurrence relation is given by:

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

For the first row and first column, the path is unique, so the cumulative sum is simply the sum along that row or column. Ensure that your solution reads input from stdin and writes the result to stdout.

inputFormat

The first line contains two integers, n and m, representing the number of rows and columns, respectively. Each of the next n lines contains m space-separated integers denoting the grid values.

outputFormat

Output a single integer indicating the maximum path score 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