Maximum Submatrix Sum

You are given a 2D matrix (or grid) of integers, which may include both positive and negative numbers. Your task is to find the submatrix (i.e. a contiguous block of cells) with the maximum possible sum. A submatrix is defined by selecting a contiguous set of rows and a contiguous set of columns.

More formally, let \(A\) be a matrix of size \(N \times M\). A submatrix is determined by four indices \(i_1, i_2, j_1, j_2\) such that \(1 \leq i_1 \leq i_2 \leq N\) and \(1 \leq j_1 \leq j_2 \leq M\). The sum of this submatrix is given by:

[ S = \sum_{i=i_1}^{i_2} \sum_{j=j_1}^{j_2} A_{ij} ]

Your solution should compute the value \(S_{max}\), the maximum submatrix sum among all possible submatrices.

The input consists of multiple test cases. Each test case represents a single matrix, and the end of input is signaled by a test case with dimensions 0 0.

inputFormat

The input is read from stdin and consists of multiple test cases. Each test case begins with a line containing two integers \(N\) and \(M\) representing the number of rows and columns in the matrix. This is followed by \(N\) lines, each containing \(M\) space-separated integers, representing the rows of the matrix. The sequence of test cases is terminated by a line with two zeros: "0 0".

Example:

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

outputFormat

For each test case, output the maximum submatrix sum on a new line to stdout.

Example:

29

## sample

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

29

</p>