Maximum Submatrix Sum

Given a matrix of integers, find the maximum sum of any submatrix. A submatrix is defined as any contiguous rectangular region of the original matrix. Mathematically, if the matrix is denoted by \(a_{ij}\), a submatrix defined by the rows \(r_1\) to \(r_2\) and columns \(c_1\) to \(c_2\) has a sum:

\[ S = \sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} a_{ij}, \]

Your task is to compute the maximum submatrix sum over all possible submatrices. It is guaranteed that the matrix contains at least one element.

inputFormat

The first line contains two space-separated integers \(N\) and \(M\), representing the number of rows and columns of the matrix. Each of the following \(N\) lines contains \(M\) space-separated integers denoting the elements of the matrix.

outputFormat

Output a single integer which is the maximum sum of any submatrix.

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

29