Contest Duration: - (local time) (100 minutes) Back to Home
E - Traveling Salesman among Aerial Cities /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

3 次元空間内に N 個の都市、都市 1 から 都市 N があります。都市 i は座標 (X_i,Y_i,Z_i) にあります。

### 制約

• 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

2
0 0 0
1 2 3


### 出力例 1

9


よって合計で 9 のコストがかかります。

### 入力例 2

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


### 出力例 2

10


### 入力例 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


Score : 500 points

### Problem Statement

In a three-dimensional space, there are N cities: City 1 through City N. City i is at point (X_i,Y_i,Z_i).

The cost it takes to travel from a city at point (a,b,c) to a city at point (p,q,r) is |p-a|+|q-b|+\max(0,r-c).

Find the minimum total cost it takes to start at City 1, visit all other cities at least once, and return to City 1.

### Constraints

• 2 \leq N \leq 17
• -10^6 \leq X_i,Y_i,Z_i \leq 10^6
• No two cities are at the same point.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 Z_1
\vdots
X_N Y_N Z_N


### Output

Print the minimum total cost it takes to start at City 1, visit all other cities at least once, and return to City 1.

### Sample Input 1

2
0 0 0
1 2 3


### Sample Output 1

9


The cost it takes to travel from City 1 to City 2 is |1-0|+|2-0|+\max(0,3-0)=6.

The cost it takes to travel from City 2 to City 1 is |0-1|+|0-2|+\max(0,0-3)=3.

Thus, the total cost will be 9.

### Sample Input 2

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


### Sample Output 2

10


For example, we can visit the cities in the order 1, 2, 1, 3, 1 to make the total cost 10. Note that we can come back to City 1 on the way.

### Sample Input 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


### Sample Output 3

6519344