Maximum Sum Rectangle in a Matrix

You are given a two-dimensional matrix of integers. Your task is to find the rectangular submatrix (a contiguous block of rows and columns) whose sum is maximum among all possible submatrices. Formally, for a matrix M with dimensions R \times C, find indices a, b, c, and d satisfying

[ 1 \le a \le b \le R, \quad 1 \le c \le d \le C ]

such that the sum

[ S = \sum_{i=a}^{b} \sum_{j=c}^{d} M_{ij} ]

is maximized.

Example:
For 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 rectangle has a sum of 29.

inputFormat

The input is read from standard input (stdin). The first line contains two integers R and C, representing the number of rows and columns respectively. Each of the next R lines contains C space-separated integers representing the elements of the matrix.

outputFormat

Output a single integer to standard output (stdout) representing the maximum sum of any rectangular submatrix within 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