题目描述

$3$ 次元空間内に $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$ 度以上巡って都市 $1$ に戻るまでの最小コストを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

都市 $1$ からスタートし、全ての都市を $1$ 度以上巡って都市 $1$ に戻るまでの最小コストを出力せよ。

题目大意

三维空间内有 $n$ 个点，坐标分别为 $(x_i,y_i,z_i)$。

从 $(a,b,c)$ 到 $(p,q,r)$ 的代价为 $|p-a|+|q-b|+\max(0,r-c)$。

求从 $1$ 号点出发，经过所有的点，返回 $1$ 号点的最小代价。

2
0 0 0
1 2 3

9

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

10

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

6519344

提示

制約

• $2\ \leq\ N\ \leq\ 17$
• $-10^6\ \leq\ X_i,Y_i,Z_i\ \leq\ 10^6$
• 同じ座標に複数の都市があることはない
• 入力は全て整数

Sample Explanation 1

都市 $1$ から都市 $2$ へ向かう時には $|1-0|+|2-0|+\max(0,3-0)=6$ のコストがかかります。 都市 $2$ から都市 $1$ へ向かう時には $|0-1|+|0-2|+\max(0,0-3)=3$ のコストがかかります。 よって合計で $9$ のコストがかかります。

Sample Explanation 2

例えば 都市 $1$, $2$, $1$, $3$, $1$ の順に移動するとコストが $10$ になります。途中で都市 $1$ に戻ってきても構いません。