{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003eマトリョーシカ\u003c/h3\u003e\n\n\u003cp\u003eマトリョーシカはロシアの民芸品として有名な人形である.\nマトリョーシカは上下に分割でき,開くと中により小さい別の人形が入っている.\n現れた小さい人形を開くとさらに小さい人形が入っている,というような入れ子構造になっている.\n\u003c/p\u003e\n\u003cdiv style\u003d\"text-align:center\"\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/c518247c67f552fa5ab54b3db809f5e0?v\u003d1715778869\" witdh\u003d\"300\" height\u003d\"300\"\u003e\n\u003cbr\u003e\n\u003c/div\u003e\n\n\u003cp\u003eあなたは旅行先で珍しい形のマトリョーシカを見つけ,\u003ci\u003eN\u003c/i\u003e 体の人形を購入した.\n\u003ci\u003ei\u003c/i\u003e 番目の人形の形状は,\u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e × y\u003csub\u003ei\u003c/sub\u003e × z\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e の直方体である.\n\u003c/p\u003e\n\n\u003cp\u003eひとしきりマトリョーシカを鑑賞したあなたは,マトリョーシカを仕舞おうとしている.\nその前に,いくつかの人形を別の人形に格納することによって必要なスペースを減らしたい.\n人形を格納する際には,まだ中にひとつも人形を格納していない人形にだけ,他の人形をひとつ格納できる.\nただし,直接的に格納される人形についてだけ数えるものとし,中に人形が入っている人形を別の人形に格納することはできる.\n\u003c/p\u003e\n\n\u003cp\u003e収納された人形は,外部から見えない状態になる.\nただし,以下の条件を満たさなければならない.\n\u003c/p\u003e\u003cul\u003e\u003cli\u003e 人形は回転してよいが,直方体のそれぞれの辺は,他方の直方体のいずれかの辺に平行\n\u003c/li\u003e\u003cli\u003e 回転後,対応する辺同士の長さそれぞれについて,収納される側の人形の長さの方が短い\n\u003c/li\u003e\u003cli\u003e 1 個の人形の中に直接収納できる人形の数は高々 1 個\n\u003c/li\u003e\u003c/ul\u003e\n\n\u003cp\u003e押入れの容積は限られているので,外部から見えている人形の体積の和を最小化したい.\nあなたの仕事は,人形を収納する操作を任意の回数繰り返して達成できる,外部から見えている人形の体積の和の最小値を求めるプログラムを作成することである.\n\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003e入力は複数のデータセットからなる.\nデータセットの個数は最大でも 50 個を超えない.\n各データセットは次の形式で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003ci\u003eN\u003c/i\u003e\u003cbr\u003e\u003ci\u003ex\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ey\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ez\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e:\u003cbr\u003e:\u003cbr\u003e\u003ci\u003ex\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ey\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ez\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\u003cp\u003e各データセットは \u003ci\u003eN + 1\u003c/i\u003e 行からなり,データセットの 1 行目には,人形の数を表す整数 \u003ci\u003eN\u003c/i\u003e が与えられる.\n続く \u003ci\u003eN\u003c/i\u003e 行の内 \u003ci\u003ei\u003c/i\u003e 行目には,\u003ci\u003ei\u003c/i\u003e 番目の人形の大きさを表す 3 つの整数 \u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e, y\u003csub\u003ei\u003c/sub\u003e, z\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e が半角スペース区切りで与えられる.\nこれらの整数は,\u003ci\u003e1 ≤ N, x\u003csub\u003ei\u003c/sub\u003e, y\u003csub\u003ei\u003c/sub\u003e, z\u003csub\u003ei\u003c/sub\u003e ≤ 100\u003c/i\u003e を満たす.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e入力の終わりは 1 つのゼロからなる行で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\u003cp\u003e各データセットについて,外部から見えている人形の体積の和の最小値を 1 行で出力せよ.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\n\u003ch3\u003eSample Input\u003c/h3\u003e\n\n\u003cpre\u003e2\n1 2 3\n4 2 3\n3\n2 5 2\n3 3 4\n5 5 5\n5\n1 1 1\n2 2 2\n3 3 3\n4 4 4\n5 5 5\n5\n1 1 1\n2 1 1\n3 1 1\n4 1 1\n5 1 1\n10\n3 1 4\n1 5 9\n2 6 5\n3 5 8\n9 7 9\n3 2 3\n8 4 6\n2 6 4\n3 3 8\n3 2 7\n0\n\u003c/pre\u003e\n\n\u003ch3\u003eOutput for Sample Input\u003c/h3\u003e\n\n\u003cpre\u003e24\n145\n125\n15\n864\u003c/pre\u003e\n"}}]}