{"problem":{"name":"Traveling Salesman among Aerial Cities","description":{"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)$. The cost it takes to travel from a city at point $(a,b,c)$ to a city at point $(p,q","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc180_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc180_e","tags":[],"sample_group":[["2\n0 0 0\n1 2 3","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$."],["3\n0 0 0\n1 1 1\n-1 -1 -1","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."],["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","6519344"]],"created_at":"2026-03-03 11:01:14"}}