1261 - 距离之和最小 V2
描述

三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小,输出这个最小的距离之和。

点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| + |y1-y2| + |z1-z2|。即3维坐标差的绝对值之和


输入

第1行:点的数量N。(2 <= N <= 10000) 第2 - N + 1行:每行3个整数,中间用空格分隔,表示点的位置。(-10^9 <= X[i], Y[i], Z[i] <= 10^9)

输出

输出最小曼哈顿距离之和。


样例

输入

4
1 1 1
-1 -1 -1
2 2 2
-2 -2 -2

输出

18
标签
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1