{"raw_statement":[{"iden":"problem statement","content":"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)$.\nThe 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)$.\nFind the minimum total cost it takes to start at City $1$, visit all other cities at least once, and return to City $1$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 17$\n*   $-10^6 \\leq X_i,Y_i,Z_i \\leq 10^6$\n*   No two cities are at the same point.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$X_1$ $Y_1$ $Z_1$\n$\\vdots$\n$X_N$ $Y_N$ $Z_N$"},{"iden":"sample input 1","content":"2\n0 0 0\n1 2 3"},{"iden":"sample output 1","content":"9\n\nThe cost it takes to travel from City $1$ to City $2$ is $|1-0|+|2-0|+\\max(0,3-0)=6$.\nThe cost it takes to travel from City $2$ to City $1$ is $|0-1|+|0-2|+\\max(0,0-3)=3$.\nThus, the total cost will be $9$."},{"iden":"sample input 2","content":"3\n0 0 0\n1 1 1\n-1 -1 -1"},{"iden":"sample output 2","content":"10\n\nFor 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."},{"iden":"sample input 3","content":"17\n14142 13562 373095\n-17320 508075 68877\n223606 -79774 9979\n-24494 -89742 783178\n26457 513110 -64591\n-282842 7124 -74619\n31622 -77660 -168379\n-33166 -24790 -3554\n346410 16151 37755\n-36055 51275 463989\n37416 -573867 73941\n-3872 -983346 207417\n412310 56256 -17661\n-42426 40687 -119285\n43588 -989435 -40674\n-447213 -59549 -99579\n45825 7569 45584"},{"iden":"sample output 3","content":"6519344"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}