n名士兵在网格中,位置用(x,y)表示,士兵可以从任何一个位置沿前、后、左、右四个方向移动。1≤n≤10000,1≤x,y≤10000。注意网格中每一个方格的位置均为正整数。
现在这n名士兵接到命令,要求向网格中某个方格集结(假设每一个方格中都能容纳无穷多个士兵),请选定一个合适的方格,使得这n名士兵移动步数总和最小。
输入文件中包含多个测试数据。每个测试数据第一行为正整数n,然后有n行,每行描述了一名士兵的初始位置x、 y。输入文件最后一行为0,表示输入结束。
对输入文件中的每个测试数据,输出n名士兵移动步数总和的最小值。
5
1 2
2 2
1 3
3 2
3 3
0
6