1486: 集结号

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:6 通过:1

题目描述

n名士兵在网格中,位置用(x,y)表示,士兵可以从任何一个位置沿前、后、左、右四个方向移动。1≤n≤100001≤x,y≤10000。注意网格中每一个方格的位置均为正整数。

现在这n名士兵接到命令,要求向网格中某个方格集结(假设每一个方格中都能容纳无穷多个士兵),请选定一个合适的方格,使得这n名士兵移动步数总和最小。

输入格式

输入文件中包含多个测试数据。每个测试数据第一行为正整数n,然后有n行,每行描述了一名士兵的初始位置x、 y。输入文件最后一行为0,表示输入结束。

输出格式

对输入文件中的每个测试数据,输出n名士兵移动步数总和的最小值。

输入样例 复制

5
1 2
2 2
1 3
3 2
3 3
0

输出样例 复制

6