A75072.空中旅行推销员

在三维空间中有 $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$ 的最小总花费。

输入以以下格式从标准输入读入。

$N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_N$ $Y_N$ $Z_N$

输出从城市 $1$ 出发，经过所有城市至少一次并最终回到城市 $1$ 的最小总花费。

样例解释 1

从城市 $1$ 到城市 $2$ 的花费为 $|1-0| + |2-0| + \max(0, 3-0) = 6$。
从城市 $2$ 回到城市 $1$ 的花费为 $|0-1| + |0-2| + \max(0, 0-3) = 3$。
因此总花费为 $9$。

样例解释 2

例如按城市 $1$、$2$、$1$、$3$、$1$ 的顺序移动，总花费为 $10$。途中可以多次回到城市 $1$。

数据范围

• $2 \leq N \leq 17$
• $-10^6 \leq X_i, Y_i, Z_i \leq 10^6$
• 不会有多个城市位于相同的坐标
• 所有输入均为整数