小珅的集装箱高塔挑战

题目描述

在智亦珅泽教育的“星际物流与空间工程”实践课上，小珅老师作为导师，正带领学徒小泽处理一批紧急的教学物资。由于最近一批星际快递包裹被提前运走，学校的模拟货运码头上遗留了许多空集装箱，把原本宽敞的空地挤得水泄不通。为了腾出足够的场地搭建临时的跨星系通讯基站，小珅决定带领大家把这些废弃集装箱堆叠成一座稳固的高塔。

每个集装箱都可以看作一个长方体，其长、宽、高均为正整数。为了方便搬运和调整重心，集装箱可以通过旋转、翻转等操作，让任意一个面朝下放置。堆叠的规则非常严格：只有当一个集装箱（称为 A）的长、宽、高都不大于另一个集装箱（称为 B）的长、宽、高时，A 才能被稳稳地堆放在 B 的上方。（注意：这里的长、宽、高是相对于当前放置状态而言的，即底面已经选定的长和宽，以及垂直向上的高度）。

例如：有两个集装箱，长宽高分别是 $(30, 45, 20)$ 和 $(35, 35, 60)$。如果直接按原始尺寸放置，它们无法直接堆叠。但如果我们把第一个集装箱立起来，使其底面变为 $(30, 20)$，高度为 $45$（记为 $(30, 20, 45)$），此时它的长和高都小于第二个集装箱的底面边长，就可以将其放在第二个集装箱上了，堆叠出来的总高度为 $105$。

小珅给小泽下了个挑战：“小泽，给定码头上的 $n$ 个集装箱的原始尺寸，请你帮我计算出，通过最优的旋转和堆叠方式，我们最多能搭出多高的高塔？”

现在，请你帮助小泽编写程序，解决这个空间规划难题。

输入格式

输入第 $1$ 行，一个整数 $n$，表示集装箱的个数。

第 $2 \sim n+1$ 行，每行三个正整数，分别表示每个集装箱的长度、宽度和高度。集装箱可以翻转和选择任意面朝下。

输出格式

输出一行，一个非负整数，表示最终能堆叠出来的最大高度。

输入输出样例

输入 #1

3
50 45 20
95 37 53
45 23 12

输出 #1

190

输入 #2

2
38 25 45
76 35 3

输出 #2

76

输入 #3

6
7 11 17
7 17 11
11 7 17
11 17 7
17 7 11
17 11 7

输出 #3

102

说明/提示

• 样例 1 解释： 最优的堆叠顺序是从下往上依次为：

  • 第 $2$ 个集装箱放在底部，选取 $53 \times 37$ 的一面朝下，高度为 $95$。
  • 第 $1$ 个集装箱放在中间，选取 $45 \times 20$ 的一面朝下，高度为 $50$。
  • 第 $3$ 个集装箱放在顶部，选取 $23 \times 12$ 的一面朝下，高度为 $45$。 总高度为 $95 + 50 + 45 = 190$。

• 样例 3 解释： 这 $6$ 个集装箱实际上是同一个长方体的不同排列（$7, 11, 17$ 的全排列）。最优策略是选取其中一个维度作为固定的高度（这里选最大的 $17$），然后将剩下的两个维度（$7$ 和 $11$）作为底面，每次堆叠时底面保持不变。这样可以堆叠 $6$ 层，总高度为 $6 \times 17 = 102$。

数据范围

• 对于 $20\%$ 的数据，$n \le 10$。
• 对于 $50\%$ 的数据，$1 \le n \le 500$，且所有集装箱的高度相同（即任意一个维度固定，另外两个维度可任意组合）。
• 另有 $10\%$ 的数据，每个集装箱都是正方体（即长、宽、高相等）。
• 对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le \text{长度}, \text{宽度}, \text{高度} \le 100000$。