Maximum Path Sum in a Grid

You are given a grid of integers with R rows and C columns. A valid path starts from any cell in the first column and ends at any cell in the last column. From a cell located at \( (i, j) \), you can move to any of the following cells in column \( j+1 \):

\( (i-1, j+1) \), \( (i, j+1) \), or \( (i+1, j+1) \) (provided that the indices are within the bounds of the grid).

Your task is to find the path that yields the maximum sum of the numbers along the way. Formally, if the grid is denoted by \( g_{i,j} \), you need to compute:

\[ \max_{0 \leq i < R}\,\{\text{max sum}(i)\}\quad\text{where}\quad \text{max\ tsum}(i)=g_{i,1}+\max_{\text{valid moves}}\{\ldots\}\]

The input consists of one or more test cases. Each test case begins with two integers \( R \) and \( C \) (separated by a space). This is followed by \( R \) lines each containing \( C \) integers. The end of input is indicated by a line with "0 0".

For each test case, print the maximum sum obtained by any valid path.

inputFormat

The input is given via standard input (stdin) and consists of multiple test cases. Each test case is formatted as follows:

• The first line contains two integers \( R \) and \( C \) representing the number of rows and columns respectively.
• The next \( R \) lines each contain \( C \) space-separated integers representing the grid.

The input terminates with a line containing "0 0" which should not be processed.

outputFormat

For each test case, output the maximum sum of a valid path from the first column to the last column. Each result should be printed on a new line on standard output (stdout).

## sample

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

12
4

</p>