Maximum Treasure Collection

You are given an n x m grid where each cell contains a non-negative integer representing the amount of treasure in that cell. A knight starts from the top-left cell (1, 1) and wants to reach the bottom-right cell (n, m). The knight can only move right or down at each step. Your task is to calculate the maximum amount of treasure the knight can collect along the path.

The knight collects the treasure in every cell he passes through, including the starting and ending cells.

Note: The grid dimensions and values can be large, so an efficient dynamic programming solution is expected.

The mathematical formulation of the solution can be expressed using the following recurrence:

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

with the base case (dp[0][0] = grid[0][0]). The answer will be (dp[n-1][m-1]).

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the number of rows and columns in the grid respectively.

The next \(n\) lines each contain \(m\) space-separated integers representing the grid values.

Example:

3 4
0 6 0 2
5 8 7 9
0 7 0 3

outputFormat

Output a single integer which is the maximum amount of treasure that can be collected from the top-left corner to the bottom-right corner.

Example:

33

## sample

3 4
0 6 0 2
5 8 7 9
0 7 0 3

33