Algorithms and Data Structures

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 1 2 -3 4 -6 -1 3 -100 4 0 0 1 -2 0 100
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

To check your solution you need to sign in
Sign in to continue