|Online MIPT programming contest||РУССКИЙ|
Time limit = 5 second(s)
Memory limit = 33000 KbIt is year 2130. Colonizers from Earth landed on one of the planets of the Alpha Centauri system. Their mission is to explore nearby planets and stars. They founded several spacecities, and developed advanced community. Now, 14 years later, they discovered that life is present in some of the nearby galaxies. Also, all the galaxies on which life is found are located so that they form a 3-dimensional rectangular array. You may assume that there exists a rectangular parallelepiped divided into cells with exactly 1 galaxy in each cell. The dimensions of the parallelepiped are integer numbers M, N and D with 1 ≤ M,N,D ≤ 20, and every cell is a cube with side 1. The government of Alpha Centauri decided to build a space zoo. The liveforms in different galaxies are different, so if a galaxy becomes a part of a zoo, it gains some profit (for different galaxies the profits are different). The main economist of the settlement Mr. Ivanoff calculated the annual profits for each galaxy. Current technology of building space constructions requires that the space zoo must be a rectangular parallelepiped with sides parallel to the sides of the parallelepiped that represents the location of galaxies. Given the results of Ivanoff's calculations, determine the highest profit or lowest loss that Alpha Centaurian government can gain from building the zoo.
Given a rectangular parallelepiped divided into cells and the numbers ascribed to the cells, determine the subparallelepiped that has the largest sum of numbers in it. You may safely assume that sum of numbers in each subparallelepiped is less than 32000.
Input The first line of input contains 3 integes M, N, D, 1 ≤ M,N,D ≤ 20. D blocks follow, each block consisting of M lines with N integers per line that represent the profit values for corresponding galaxies. Profits and losses (the latter represented as negatve profits) are less than or equal to 500 in magnitude.
Output Output should contain a single number the highest profit (or the lower loss) possible.
1 1 1 1
2 2 2 2 -1 -2 2 -2 2 2 -1
2 2 2 -2 -3 -5 -4 -6 -7 -9 -8
2 3 4 1 1 1 1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1
Idea by Smolyakov Andrey & Alex
Desctiption and tester by Malyh Anton.
© acm.mipt DevGroup
The page was generated in 230ms