Maximum Gold Collection

You are given a grid with m rows and n columns. Each cell contains a non-negative integer representing the number of gold coins at that cell. You start at the top-left cell (i.e., cell (0,0)) and your goal is to reach the bottom-right cell (i.e., cell (m-1, n-1)). You may only move either to the right or down at each step.

Your task is to determine the maximum number of gold coins you can collect along a path from the start to the destination.

The problem can be formulated using dynamic programming. Let \(dp(i,j)\) denote the maximum coins collected to reach cell \((i,j)\). The recurrence relation is: \[ \begin{aligned} dp(i,j) &= grid(i,j) + \max\{ dp(i-1,j),\ dp(i,j-1) \} \\ \end{aligned} \] with the base case \(dp(0,0) = grid(0,0)\) and handling the first row and first column appropriately.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two space-separated integers, m and n, representing the number of rows and columns respectively.
• The following m lines each contain n space-separated integers that represent the grid.

Example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

Output a single integer to standard output (stdout) which is the maximum gold coins that can be collected from the top-left cell to the bottom-right cell.

Example:

12

## sample

3 3
1 3 1
1 5 1
4 2 1

12