Maximum Sum Submatrix

You are given an \( n \times m \) matrix with integer elements. Your task is to find the maximum sum of any non-empty submatrix of the given matrix. A submatrix is defined as a contiguous block of elements, i.e., for indices \( 1 \leq i \leq j \leq n \) and \( 1 \leq k \leq l \leq m \), the submatrix is \( A[i \ldots j][k \ldots l] \).

The problem can be formalized as follows: Given a matrix \( A \) of size \( n \times m \), find \[ \max_{1 \le i \le j \le n,\; 1 \le k \le l \le m} \sum_{p=i}^{j} \sum_{q=k}^{l} A_{p,q} \] Note that the submatrix must contain at least one element.

For example, consider the matrix:

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

The maximum sum submatrix in this case has a sum of 29.

inputFormat

The input is given via standard input (stdin) with the following format:

n m
A[1][1] A[1][2] ... A[1][m]
A[2][1] A[2][2] ... A[2][m]
...
A[n][1] A[n][2] ... A[n][m]

Here, \( n \) is the number of rows and \( m \) is the number of columns.

outputFormat

Output a single integer (via stdout) which is the maximum sum of any non-empty submatrix of the given matrix.

## sample

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

29