Omax

Problem code: OMAX

All submissions for this problem are available.

Given a matrix sized m x n, we define an O-region as a non-empty sub-block with another non-empty sub-block inside removed, such that the removed sub-block has no common boundaries with the outside. That is, the leftmost column of the removed sub-block must be different from the leftmost column of the outer sub-block, and similarly the rightmost columns, topmost rows, and bottommost rows are different. The removal of the inner sub-block leaves a region which looks like the letter O.

The value of an O-region is the sum of all numbers in the outer sub-block but not in the removed one. Your task is finding the maximal value of all O-regions appearing in the given matrix.

Input

There are several test cases (fifteen at most), each formed as follows:

  • The first line contains two positive integers m, n (3 ? m, n ? 77).
  • m lines follow, each containing n integers (each having an absolute value of 105 at most) describing the matrix.
The input is ended with m = n = 0.

Output

For each test case, output on a line an integer which is the respective maximal value found.

Example

Input:
3 3
1 1 1
1 3 -1
1 1 1
4 5
1 -2 3 -4 5
-5 4 -3 2 -1
1 -3 5 -7 9
-9 7 -5 3 -1
0 0
Output:
6
19
Author: anhdq
Date Added: 30-01-2011
Time Limit: 15 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

i think that in last example

null_pointer @ 16 Mar 2011 10:10 AM

i think that in last example ans=19 is wrong,kindly justify the answer

The maximum of 19 in the

brianfry713 @ 6 Jan 2012 10:52 AM
The maximum of 19 in the second case is the outer block from 2nd column to 5th column with only the -7 inside removed. The top and left of the outer block have width 2, the right and bottom have width 1.

what should be the output for

mycontest @ 5 May 2012 12:48 PM
what should be the output for the impossible cases? like: 3 3 -1 -1 -1 -1 -1 -1 -1 -1 -1

-8?

wtq4er @ 16 May 2012 11:31 AM
-8?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions