Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation

• # 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: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB