Maximum submatrix
Given an matrix of integers, you are asked to calculate the submatrix with the maximum sum.
Input
The first line of the input contains two integers - the number of rows in the matrix r and the number of columns c (1 ≤ r, c ≤ 50).
The next r lines contain c integers separated by a space, that represent the elements in the matrix .
Output
The program should print a single integer - the largest submatrix sum.
Examples
Input | Output |
|---|---|
3 5 | 104 |
Explanation
1 | 2 | -3 | 4 | -6 |
-1 | 3 | -100 | 4 | 0 |
0 | 1 | -2 | 0 | 100 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB