Under construction

Still being built. Things may change

Maximum Submatrix Sum

Interview

Time limit2sMemory limit128 MB

Summary
Given an N by M integer matrix, find the maximum possible sum over all contiguous rectangular submatrices.
Level

Medium6 of 10

Topics
Dynamic programming, Matrix, Array, Prefix sum
Solved
No attempts yet

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.

Examples1

  1. Example 1

    Input
    3 5
2 3 -21 -22 -23
5 6 -22 -23 -25
-22 -23 4 10 2
    Expected output
    16