Maximum Gold Collection

You are given a dungeon represented as a grid of size \(m \times n\). Each cell in the grid contains a non-negative integer representing the amount of gold present in that cell. Starting from the top-left cell (1,1), you must move to the bottom-right cell (m,n) by only moving right or down. Your goal is to collect as much gold as possible along the path.

The amount of gold collected along a path is the sum of the gold values in the cells visited. You need to determine the maximum amount of gold you can collect when you reach the bottom-right cell.

Input constraints: \(1 \leq m, n \leq 1000\) and all cell values are non-negative integers.

Hint: Consider using dynamic programming where each state represents the maximum gold that can be collected up to that cell:

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

inputFormat

The input is given via standard input (stdin). The first line contains two integers, \(m\) and \(n\), representing the number of rows and columns in the grid respectively. The next \(m\) lines each contain \(n\) space-separated integers, representing the gold values in the grid.

For example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Output a single integer to standard output (stdout) which represents the maximum amount of gold that can be collected when reaching the bottom-right cell.

For the above example, the output should be:

12

## sample

3 3
1 3 1
1 5 1
4 2 1

12