C. 立方体

• 时间限制：每个测试点 3 秒
• 内存限制：1024 MB
  

你有一个 $n \times n \times n$ 的三维立方体，里面包含 $n^3$ 个整数。
你需要从中选出 $n$ 个数，使得它们的和尽可能小。

但是，禁止选择位于同一平面内的两个数。具体来说，如果我们用三个笛卡尔坐标 $(x,y,z)$ 来表示立方体中的位置，则选择位置 $(x,y,z)$ 和 $(x',y',z')$ 的两个数是禁止的，如果：

$x = x'$ 或 $y = y'$ 或 $z = z'$。

换句话说，不允许有两个选出的数在任何一维上坐标相同，相当于选出的 $n$ 个数的 $x$ 坐标互不相同，$y$ 坐标互不相同，$z$ 坐标互不相同（即构成了一个 $n$ 皇后问题在三维中的变体，但这里皇后是所有格点）。

输入格式

第一行是一个整数 $n$。
接下来有 $n^2$ 行，每行有 $n$ 个整数。

这些行对应立方体的每一层（按 $x$、$y$ 顺序给出）。
更准确地说，对于每个 $(x, y, z)$（$1 \le x, y, z \le n$），位于位置 $(x, y, z)$ 的数出现在：

• 行号 = $(x-1) \times n + y$
• 该行的第 $z$ 个数

约束：

• $2 \le n \le 12$
• 立方体内所有数均为 $0$ 到 $2 \times 10^7$ 之间的整数。

输出格式

输出一个整数，表示符合上述规则选出的 $n$ 个数的最小可能和。

样例

输入

3
1 2 3
4 5 6
7 8 9
1 1 1
2 2 2
3 3 3
4 3 0
2 1 4
9 8 9

输出

5