题目描述

在一个三维空间中，有 $N$ 个城市：从城市 1 到城市 $N$。第 $i$ 个城市位于坐标 $(X_i, Y_i, Z_i)$ 处。

从坐标为 $(a, b, c)$ 的城市到坐标为 $(p, q, r)$ 的城市的旅行成本为 $|p-a|+|q-b|+\max(0,r-c)$。

找出从城市 1 出发，至少访问其他所有城市一次，然后返回城市 1 的最小总成本。

约束条件

• $2 \leq N \leq 17$
• $-10^6 \leq X_i, Y_i, Z_i \leq 10^6$
• 没有两个城市位于同一点
• 输入的所有值都是整数

输入

输入以以下格式从标准输入中给出：

$N$ $X_1$ $Y_1$ $Z_1$ $\vdots$ $X_N$ $Y_N$ $Z_N$

输出

打印从城市 1 出发，至少访问其他所有城市一次，然后返回城市 1 的最小总成本。

示例输入 1

2
0 0 0
1 2 3

示例输出 1

9

从城市 1 到城市 2 的旅行成本为 $|1-0|+|2-0|+\max(0,3-0)=6$。

从城市 2 到城市 1 的旅行成本为 $|0-1|+|0-2|+\max(0,0-3)=3$。

因此，总成本为 $9$。

示例输入 2

3
0 0 0
1 1 1
-1 -1 -1

示例输出 2

10

例如，我们可以按顺序访问城市 1、城市 2、城市 1、城市 3、城市 1，使总成本为 $10$。请注意，我们可以在路上返回城市 1。

示例输入 3

17
14142 13562 373095
-17320 508075 68877
223606 -79774 9979
-24494 -89742 783178
26457 513110 -64591
-282842 7124 -74619
31622 -77660 -168379
-33166 -24790 -3554
346410 16151 37755
-36055 51275 463989
37416 -573867 73941
-3872 -983346 207417
412310 56256 -17661
-42426 40687 -119285
43588 -989435 -40674
-447213 -59549 -99579
45825 7569 45584

示例输出 3

6519344