cho.sh
Notes
Loading...

Maximum Submatrix Sum

Time limit

2s

Memory limit

128 MB

Problem

An N x M matrix contains one integer in each cell. In this game, choose one non-empty submatrix formed by consecutive rows and consecutive columns, and score it by summing every integer inside it.

Find the largest possible score among all such submatrices.

Input

The first line contains N and M (1 < N < 200, 1 < M < 200). Each of the next N lines contains M integers. Every integer is between -10,000 and 10,000, inclusive.

Output

Print the maximum possible sum of a submatrix on the first line.