Maximum Submatrix Sum

Find the maximum sum of any rectangular submatrix within a given 2D matrix.

Given an (m \times n) matrix (A), a submatrix is defined by two pairs of indices representing its upper-left and bottom-right corners. The submatrix must consist of contiguous elements and can be as small as a single element.

For example, for the matrix:
[ \begin{bmatrix} -1 & 2 & -1 \ 1 & -2 & 3 \ -1 & 2 & 4 \end{bmatrix} ] The maximum submatrix sum is 8.

inputFormat

The first line contains two integers (m) and (n) — the number of rows and columns of the matrix, respectively.
Each of the next (m) lines contains (n) space-separated integers representing the elements of the matrix.

outputFormat

Output a single integer, which is the maximum sum over all possible submatrices.## sample

3 3
-1 2 -1
1 -2 3
-1 2 4

8