Maximum Sum Submatrix

You are given a matrix with n rows and m columns. Your task is to find the submatrix (a contiguous block of rows and columns, with at least one cell) whose sum of elements is maximum. Formally, if the matrix is \(A\) and a submatrix is defined by two pairs of indices \( (r1, c1) \) and \( (r2, c2) \) such that \(1 \le r1 \le r2 \le n\) and \(1 \le c1 \le c2 \le m\), you need to compute:

[ \text{maxSum} = \max_{1 \le r1 \le r2 \le n,\ 1 \le c1 \le c2 \le m} \sum_{i=r1}^{r2}\sum_{j=c1}^{c2} A_{ij} ]

The matrix may contain positive, negative, or zero values. It is guaranteed that there is at least one cell in the matrix.

Note: In the case where all elements are negative, the maximum sum is the largest (i.e. the least negative) element.

inputFormat

The first line of input contains two integers n and m, representing the number of rows and columns respectively.

Then follow n lines, each containing m integers separated by spaces, which represent the matrix.

outputFormat

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

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

29