11363: uva10755 - Garbage Heap
Description
Farmer John has a heap of garbage formed in a rectangular paral lelepiped.
It consists of $A × B ×C$ garbage pieces each of which has a value. The value of a piece may be $0$, if the piece is neither profitable nor harmful, and may be negative which means that the piece is not just unprofitable, but even harmful (for environment).
The farmer thinks that he has too much harmful garbage, so he wants to decrease the heap size, leaving a rectangular nonempty paral lelepiped of smaller size cut of the original heap to maximize the sum of the values of the garbage pieces in it. You have to find the optimal parallelepiped value. (Actu ally, if all smaller parallelepiped has value less than the original one, the farmer will leave the original parallelepiped).
Input
The first line of the input contains the number of the test cases, which is at most $15$.
The desc
The first line of a test case desc
The next lines contain $A·B ·C$ numbers, which are the values of garbage pieces. Each number does not exceed $2^{31}$ by absolute value. If we introduce coordinates in the parallelepiped such that the cell in one corner is $(1,1,1)$ and the cell in the opposite corner is $(A,B,C)$, then the values are listed in the order
(1, 1,1),(1,1,2),...,(1,1,C),
(1, 2,1),...,(1,2,C),...,(1,B,C),
(2, 1,1),...,(2,B,C),...,(A,B,C).
The test cases are separated by blank lines.
Output
Sample 1 Input
1
2 2 2
-1 2 0 -3 -2 -1 1 5
Sample 1 Output
6