AT_abc180_e [ABC180E] Traveling Salesman among Aerial Cities

[problemUrl]: https://atcoder.jp/contests/abc180/tasks/abc180_e $ 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 $ に戻るまでの最小コストを出力せよ。

### 制約 - $ 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 $ に戻ってきても構いません。