Given a cube of positive and negative integers, find the sub-cube with the largest sum.The sum of a cube is the sum of all the elements in that cube. In this problem, the sub-cube with the largest sum is referred to as the maximal sub-cube.

给出一个正整数和负整数组成的立方体，找出其中具有最大和的子立方体。所谓一个立方体的和是指这个立方体中所有元素的和。

A sub-cube is any contiguous sub-array of size 1x1x1 or greater located within the whole array.

一个子立方体是指在整个array中的任何大于或等于1x1x1的连续的子array。

As an example, if a cube is formed by following 3x3x3 integers：
例如，由下列3x3x3 整数组成的立方体：

0 -1 3
-5 7 4
-8 9 1

-1 -3 -1
2 -1 5
0 -1 3

3 1 -1
1 3 2
1 -2 1

Then its maximal sub-cube which has sum 31 is as follows:
那么它的最大子立方体的和是31,如下所示：

7 4
9 1

-1 5
-1 3

3 2
-2 1

Input

Each input set consists of two parts. The first line of the input set is a single positive integer N between 1 and 20, followed by NxNxN integers separated by white-spaces (newlines or spaces). These integers make up the array in a plane, row-major order (i.e., all numbers on the first plane, first row, left-to-right, then the first plane, second row, left-to-right, etc.). The numbers in the array will be in the range [-127,127].

每个输入集中包括两部分。输入集的第一行是一个正整数N，在1和20之间，紧跟着用空格（空行）等分隔的NxNxN个整数。这些整数用行序的平面形式组成了一个array（比如，在第一个平面中的所有数字，第一行，从左到右，然后第一个平面，第二行，从左到右，等等）。array中的数在 [-127,127] 之间。

The input is terminated by a value 0 for N.

输入用0来终止。

Output

The output is the sum of the maximal sub-cube.

输出最大子立方体的和。

Sample Input

3
0 -1 3
-5 7 4
-8 9 1
-1 -3 -1
2 -1 5
0 -1 3
3 1 -1
1 3 2
1 -2 1
0

Sample Output

31

Source

asia 97

[此贴子已经被作者于2006-7-13 19:34:12编辑过]