Practice Dynamic programming with the exercise "Max Rect"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Dynamic programming

Statement

Goal

Given a 2D array of positive and negative integers, try finding out the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all its elements. A sub-rectangle can be of any size from 1x1 to the max area of the whole rectangle, and can be located anywhere within the whole rectangle.

Input

Line 1: W H for the width and height of the whole rectangle
Next H lines: space separated integers. Each line contains one row of data for the rectangle

Output

The sum of the "maximum" sub-rectangle

Constraints

1 ≤ W, H ≤ 100
-99 ≤ n ≤ 99, where n is any integer within the rectangle
No data line is longer than 500 characters

Example

Input

2 2
5 -9
6 9

Output

Solve it

A higher resolution is required to access the IDE