第4题 旅行商

有三维立体空间里，有n个城市，第i个城市的坐标是(x[i],y[i],z[i])。

从第i个城市到第j个城市的距离dis[i][j] = abs(x[j]-x[i]) + abs(y[j]-y[i]) + max(0,z[j]-z[i])，其中abs是求绝对值。

你需要从1号城市出发，遍历每一个城市至少一次，最后回到1号城市，问最少的旅行距离。

输入格式 第一行，一个整数n。2<=n<=17。

接下来有n行，第i行有三个整数：x[i],y[i],z[i]。-1e6<=x[i],y[i],z[i]<=1e6。

所有的城市坐标不会重叠。

输出格式 一个整数。

输入/输出例子1 输入：

2

0 0 0

1 2 3

输出：

9

输入/输出例子2

输入：

3

0 0 0

1 1 1

-1 -1 -1

输出：

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

输出：

6519344