Maximum Sum Rectangular Submatrix

You are given a two-dimensional matrix with n rows and m columns. Your task is to find the rectangular submatrix which has the maximum sum of its elements. In other words, you need to select a contiguous block of rows and columns whose total sum is maximized.

The problem can be formalized as follows. Given a matrix \(A\) of size \(n \times m\), find indices \(1 \leq r_1 \leq r_2 \leq n\) and \(1 \leq c_1 \leq c_2 \leq m\) such that the sum \[ S = \sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} A_{i,j} \] is maximized. If the matrix contains all negative numbers, the answer is the maximum element in the matrix.

This problem can be efficiently solved using an algorithm that applies Kadane's algorithm on a compressed one-dimensional array for every pair of columns.

inputFormat

The first line contains two space-separated integers n and m (the numbers of rows and columns respectively). The next n lines each contain m space-separated integers representing the elements of the matrix.

For example:

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

outputFormat

Output a single integer representing the maximum sum of a rectangular submatrix in the given matrix.

For the example above, the output should be:

29

## sample

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

29