问题描述

AtCoder正在开发一种教育玩具，该玩具通过组合积木来创建一个具有指定轮廓的三维物体。玩具由一组多立方体形状的积木和一对二维单色轮廓图像组成。如果你可以将积木组合成一个三维物体，使得所创建物体的正面和右侧的两个轮廓与给定的轮廓图像完全匹配，则你将赢得游戏。

为了让孩子们能够长时间地玩耍，我们希望为一套积木准备多对轮廓。例如，左图中显示的6块积木可以用来创建两对轮廓，如右图所示。

作为玩具设计师，你会得到两对正面和右侧的轮廓图像，你的任务是找到一组可以从中构建两个具有给定轮廓对的物体的积木，并找到构建它们的方式。由于孩子们可能会不小心吞下小积木，所以只由少量大积木组成的积木集合更好。

详细难题规则

• 您不必使用所有的积木（但如果使用所有积木，得分会更高）。
• 每个积木可以绕x轴、y轴和z轴旋转90度，但不能翻转。
• 积木必须按照每个顶点具有整数坐标的方式排列，并且不同的积木不能有正的共同体积。
• 所构建的物体不必是连通的。为了简化起见，我们假设可以进行浮动排列（您可以将其理解为有大量额外的透明积木，可以用于支撑积木）。

关于轮廓

从左到右取x轴，从前到后取y轴，从上到下取z轴。我们假设所有的积木都在一个立方体区域内，该区域的对角线顶点为$(0,0,0)$和$(D,D,D)$。我们定义一个三维01数组 $b(x,y,z)$ ，如果某个积木占据了以$(x,y,z)$ 和 $(x+1,y+1,z+1)$ 为对角线的立方体区域，则$b(x,y,z)=1$；否则$b(x,y,z)=0$。然后，从正面看的轮廓是一个二维01数组 $f(z,x)$，如下所示：

\[ f(z,x)=\begin{cases} 1&(\sum_{y=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{y=0}^{D-1}b(x,y,z)=0) \end{cases} \]

类似地，从右侧看的轮廓是一个二维01数组 $r(z,y)$，如下所示：

\[ r(z,y)=\begin{cases} 1&(\sum_{x=0}^{D-1}b(x,y,z)\geq 1)\\ 0&(\sum_{x=0}^{D-1}b(x,y,z)=0) \end{cases} \]

计分

设$v_1,\\cdots,v_n$是创建玩具积木集合中每个积木的体积。这里，一个积木的体积等于它包括的$1\\times 1\\times 1$方块的数量。每个积木必须是连通的，即它包含的每个方块都可以通过共享的面进行移动到达。如果有一个不连通的积木，则会判断为WA。