A C M I C P C2008 South A merican Regionals

Problem C

Source le name: candy.c, candy.cpp or candy.java Lit tle Charlie is a nice boy addicted to candies. He is even a subscriber to A ll C andies Magazine and was selected to participate in the International C andy Picking Contest. In this contest a random number of boxes containing candies are disposed in M rows with N columns each (so, there are a total of M N boxes). E ach box has a number indicating how many candies it contains. T he contestant can pick a box (any one) and get all the candies it contains. But there is a catch (there is always a catch): when choosing a box, all the boxes from the rows immediately above and immediately below are emptied, as well as the box to the left and the box to the right of the chosen box. T he contestant continues to pick a box until there are no candies left. T he gure bellow illustrates this, step by step. E ach cell represents one box and the number of candies it contains. A t each step, the chosen box is circled and the shaded cells represent the boxes that will be emptied. A fter eight steps the game is over and Charlie picked 10 + 9 + 8 + 3 + 7 + 6 + 10 + 1 = 54 candies.
For small values of M and N , Charlie can easily nd the maximum number of candies he can pick, but when the numbers are really large he gets completely lost. C an you help Charlie maximize the number of candies he can pick?
T he input contains several test cases. T he rst line of a test case contains two positive integers M and N (1 M N 105 ), separated by a single space, indicating the number of rows and columns respectively. E ach of the following M lines contains N integers separated by single
spaces, each representing the initial number of candies in the corresponding box. E ach box will have initially at least 1 and at most 103 candies. T he end of input is indicated by a line containing two zeroes separated by a single space. The input must be read from standard input.

Output

For each test case in the input, your program must print a single line, containing a single value, the integer indicating the maximum number of candies that Charlie can pick. The output must be written to standard output. Sample input 0 Output for the sample input 17