给你一个 $$$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$$$ 个数字。
- $$$2 \leq n \leq 12$$$
- 立方体中的所有数字都是 $$$0$$$ 和 $$$2\times 10^7$$$ 之间的整数。
输出
输出由单个数字组成。它是根据上述规则从立方体中选择的 $$$n$$$ 个数字的最小和。
示例
输入 #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