fb pixel

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
Β 
To check your solution you need to sign in
Sign in to continue