B. AIMC Lab
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Your AIMC Lab has developed an entirely new three-dimensional quantum matrix!

Consider a three-dimensional grid of size $$$N \times M \times H$$$, with coordinates $$$1 \le x \le N$$$, $$$1 \le y \le M$$$, and $$$1 \le z \le H$$$. A qubit occupies every integer grid point. Let $$$(x_u,y_u,z_u)$$$ be the coordinates of qubit $$$u$$$.

For any two qubits $$$u$$$ and $$$v$$$, define their squared spatial distance as $$$$$$ d^2(u, v) = (x_u - x_v)^2 + (y_u - y_v)^2 + (z_u - z_v)^2. $$$$$$

The system has eight energy matrices $$$A_{D,c}$$$, each of size $$$N \times M \times H$$$, indexed by integers $$$0 \le D \le 3$$$ and $$$0 \le c \le 1$$$.

You may initialize each qubit to either basis state $$$|0\rangle$$$ or $$$|1\rangle$$$. Its corresponding basis-state value is $$$c_P=0$$$ or $$$c_P=1$$$.

After initialization, the total energy is calculated as follows:

  • For each integer pair $$$0 \le D \le 3$$$, $$$0 \le c \le 1$$$, qubit $$$P$$$ gains $$$A_{D,c}(x_P,y_P,z_P)$$$ energy if and only if:
    • The basis-state value of $$$P$$$ satisfies $$$c_P=c$$$.
    • For every qubit $$$Q$$$ with $$$d^2(P,Q)=D$$$, the value $$$c_P+c_Q+D$$$ is even.

As the chief scientist of AIMC Lab, initialize every qubit to a basis state so that the system's total energy is maximized. Output this maximum energy.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$H$$$ ($$$1 \le N,M,H \le 100$$$ and $$$N \times M \times H \le 100$$$), the grid dimensions.

The data for the eight energy matrices $$$A_{D,c}$$$ follow in lexicographic order of $$$(D,c)$$$.

Each matrix consists of $$$N$$$ blocks. Each block has $$$M$$$ lines, each containing $$$H$$$ integers. Blocks are separated by blank lines.

The $$$z$$$-th number in the $$$y$$$-th line of the $$$x$$$-th block is the energy at $$$(x,y,z)$$$. All energy values satisfy $$$A_{D,c}(x_P,y_P,z_P) \in [0,10^9]$$$.

Output

Output one integer: the maximum total energy the system can achieve.

Examples
Input
1 1 1
3

5

100

200

1000

2000

50

60
Output
2265
Input
2 2 2
1 1
1 1

1 1
1 1

0 0
0 0

0 0
0 0

0 0
0 0

0 0
0 0

0 0
0 0

0 0
0 0

10 10
10 10

10 10
10 10

0 0
0 0

0 0
0 0

0 0
0 0

0 0
0 0

0 0
0 0

0 0
0 0
Output
88
Note

Sample 1 Explanation

The grid contains only one qubit, at $$$(1,1,1)$$$.

Initializing it to $$$|1\rangle$$$ gives $$$A_{0,1}(1,1,1)+A_{1,1}(1,1,1)+A_{2,1}(1,1,1)+A_{3,1}(1,1,1)=5+200+2000+60=2265$$$, which is optimal.

Sample 2 Explanation

Initialize all $$$8$$$ qubits of the $$$2 \times 2 \times 2$$$ grid to $$$|0\rangle$$$.

  • Each qubit gains $$$1$$$ energy from $$$A_{0,0}$$$, for a total of $$$8$$$.
  • All qubits at squared distance $$$2$$$ are also in state $$$|0\rangle$$$, so each qubit gains $$$10$$$ from $$$A_{2,0}$$$, for a total of $$$80$$$.

The total energy is $$$8+80=88$$$. This can be shown to be the maximum.