Illuminated Crystal Cube

Mr. Jin created a special crystal cube of side length \(a\) using \(a^3\) unit \(1 \times 1 \times 1\) crystal blocks as a gift for his beloved who, though nameless, is gentle, brave, and kind. However, due to the difficulties of transport for such a bulky gift, he disassembled the cube into its individual blocks before sending it.

Once received, his beloved quickly reassembled the cube. At night, she finds that exactly \(n\) of these crystal blocks randomly emit a penetrating beam of light in one of the six axis–parallel directions (up, down, left, right, front, back) with equal probability. Only the blocks that do not emit light have a defined beauty value. The overall night‐time beauty of the cube is the sum of the beauty values of those non–emitter blocks that are hit by at least one light beam.

Your task is: given the side length \(a\), the number \(n\) of blocks that will emit light, and the beauty values of all \(a^3\) blocks (in a fixed order), choose exactly \(n\) blocks to be emitters and assign each a direction such that the union of their light beams (which pass through all blocks along the chosen axis–direction) gives the minimum and maximum possible overall beauty. Note that a block that is chosen as an emitter is not counted even if it would have been lit by another beam.

Important: If an emitter is placed on a boundary, it may be oriented so that its beam immediately leaves the cube, producing no illumination.

All formulas must be written in \(\LaTeX\) format.

inputFormat

The input begins with two integers \(a\) and \(n\) where \(a\) is the side length of the cube and \(n\) is the number of light–emitting blocks. Following that are \(a^3\) integers representing the beauty values of the blocks. The order of these values is in layer–major order: for \(z = 0, 1, \dots, a-1\), for \(y = 0, 1, \dots, a-1\), and for \(x = 0, 1, \dots, a-1\).

outputFormat

Output two integers separated by a space: the minimum overall beauty and the maximum overall beauty possible under the optimal choices of emitter placements and orientations.

sample

1 0
10

0 0