Maximum Subgrid Sum

You are given a 2D grid (matrix) of integers. Your task is to find the maximum sum of any contiguous rectangular subgrid within the given grid. In other words, you must choose a submatrix of the grid such that the sum of its elements is maximum. This problem can be efficiently solved by extending Kadane's algorithm for 1D arrays into 2D.

The input consists of multiple test cases. Each test case starts with two integers R and C (the number of rows and columns respectively) followed by R lines, each containing C space-separated integers. The input terminates with a test case where both R and C are 0; this case should not be processed.

Hint: Use the idea of fixing left and right column boundaries and applying Kadane's algorithm on the compressed 1D array (summing rows between these boundaries) to find the maximum sum for that particular column pair.

inputFormat

The input is given via standard input and consists of multiple test cases. For each test case:

• The first line contains two integers R and C separated by a space.
• This is followed by R lines, each with C space-separated integers representing the grid.

The sequence of test cases ends with a line "0 0", which should not be processed.

outputFormat

For each test case, output a single line containing the maximum sum of any contiguous rectangular subgrid from the given grid.

## sample

4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6
3 3
1 2 3
4 5 6
7 8 9
0 0

29
45

</p>