Maximum Sum

Time Limit: 1 Second    Memory Limit: 32768 KB

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.

As an example, if a cube is formed by following 3x3x3 integers:

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:

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].

The input is terminated by a value 0 for N.

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

Submit

Source: Asia 1997, Shanghai (Mainland China)