给你一个大小为 $n \times n \times n$ 的三维大立方体，其中包含 $n^3$ 个数字。你需要选择其中的 $n$ 个数字，使得它们的和尽可能小。然而，禁止选择位于同一平面上的两个数字。也就是说，如果我们用三个笛卡尔坐标来确定立方体中的位置，那么如果 $x = x'$、$y = y'$ 或 $z = z'$，则禁止同时选择位置 $(x, y, z)$ 和 $(x', y', z')$ 处的两个数字。

输入格式

输入包含数字 $n$，后面跟着立方体中的 $n^3$ 个数字。这些数字以 $n$ 个二维矩阵的形式给出，每个矩阵对应立方体的一个层。更具体地说，接下来会有 $n^2$ 行，每行有 $n$ 个数字。对于每个 $x, y, z$ ($1 \le x, y, z \le n$)，位置 $(x, y, z)$ 处的数字是第 $((x - 1) \times n + y)$ 行中的第 $z$ 个数字。

输出格式

输出包含一个数字，表示根据上述规则从立方体中选择 $n$ 个数字的最小和。

数据范围

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

样例

输入 1

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

输出 1

5