Description

Mr. Jin has a girlfriend without a name. She is hardworking, brave, wise, and kind. Mr. Jin likes her very much. To this end, he used $a^3$ unique $1\times 1 \times 1$ crystal blocks to make a crystal cube with side length $a$. He wants to give this crystal cube to the purest and kindest girl he has ever met.

Because the crystal cube is too big to transport, Mr. Jin decided to take it apart before sending it. He believes that reassembling the crystal cube will not be difficult for her, since she is smart.

After receiving the gift, the nameless girl quickly reassembled the crystal cube according to the instructions. She found that there are $n$ crystals which, in a dark and quiet night, randomly emit a penetrating beam in one of the six directions (up, down, left, right, front, back) with equal probability. Crystals that are illuminated by the beams look especially beautiful. For each crystal that does not emit light, she defined a beauty value. The beauty of the crystal cube at night is the sum of the beauty values of all illuminated crystals. She wants to know the minimum and maximum possible beauty of the crystal cube at night.

Input Format

The first line contains $a$, the side length of the crystal cube. Then follow $a^3$ lines, each containing several integers. The first number $g_i$ is the beauty value of the $i$‑th crystal. If $g_i = 0$, this crystal emits light. Then follow 3 to 6 integers, which are the indices of crystals that share a face with this crystal.

Output Format

Output two integers: the minimum and the maximum possible beauty of the crystal cube at night.

2
0 7 2 3
0 8 1 4
4 5 4 1
8 6 3 2
16 3 6 7
32 4 5 8
1 1 8 5
2 2 7 6

0 12

Hint

For all testdata, $1 < a \leq 70$, $g_i < 10^6$, $n \leq 8$.

Translated by ChatGPT 5