Max Wheat Collection

You are given an \(M \times N\) grid where each cell \(grid[i][j]\) holds the number of wheat units. A farmer starts at the top-left cell and must travel to the bottom-right cell, but he can only move either right or down at each step.

The goal is to maximize the total number of wheat units collected along the path. This problem can be solved using dynamic programming. The recurrence relation is given by: \[ dp[i][j] = \max(dp[i-1][j],\, dp[i][j-1]) + grid[i][j] \] with appropriate initialization for the top row and left column.

Input is read from standard input and output to standard output.

inputFormat

The first line contains two integers \(M\) and \(N\) representing the number of rows and columns. Each of the next \(M\) lines contains \(N\) space-separated integers denoting the wheat units in each cell of the corresponding row.

outputFormat

Output a single integer, which is the maximum wheat units that can be collected from the top-left cell to the bottom-right cell.

3 3
1 3 1
1 5 1
4 2 1

12