Description
Given a carpet, it has some numbers on it. It can be represented by a n*m rectangle and each square has its own value.
For example:
You are asked to cut out a piece of carpet (should not be empty) so that the sum of the numbers in it is the greatest.
In this example, you should cut out the blue part whose total sum is 110. Note that the cut-out part must be a rectangle too.
Input
Given two positive integers n and m in the first line.
Next, there're n lines, each containing m signed integers (ci1 ci2 ci3 ... cim), which represent the carpet.
Constraints:
|cij| <= 1000 for all test cases
- 50%: min{n,m} = 1, n*m <=105
- 25%: max{n,m} <= 20
- 25%: max{n,m} <= 80
Output
Output a single line containing the largest sum of the carpet you cut out.
Remember to print '\n'.