Collect Maximum Coins

You are given one or more grids of integers representing coin values. Your task is to compute the maximum number of coins one can collect when moving from the top-left corner to the bottom-right corner of each grid. From any cell, you may only move right or down. The recurrence relation for the dynamic programming solution can be written in LaTeX as follows: $$dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + grid[i][j].$$

The input consists of several test cases. Each test case starts with two integers \(N\) and \(M\) denoting the number of rows and columns of the grid respectively, followed by \(N\) lines each containing \(M\) integers. A test case with \(N = 0\) and \(M = 0\) marks the end of the input.

inputFormat

The input is read from standard input (stdin) and contains one or more test cases.

• The first line of each test case contains two positive integers \(N\) and \(M\) (\(1 \le N, M \le\) reasonable limits) representing the number of rows and columns respectively.
• This is followed by \(N\) lines, each with \(M\) integers separated by spaces, representing the grid cells.
• The input terminates with a line containing "0 0".

outputFormat

For each test case, output the maximum number of coins that can be collected from the top-left to the bottom-right corner. Each answer should be printed on a new line to the standard output (stdout).

3 3
1 3 1
1 5 1
4 2 1
0 0

12