问题 2216. -- 士兵 Soldiers

2216: 士兵 Soldiers

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 2
[提交][状态][讨论版]

题目描述

格格兰郡的N名士兵随机散落在全郡各地。格格兰郡中的位置由一对(x,y)整数坐标表示。
士兵可以进行移动,每次移动,一名士兵可以向上,向下,向左或向右移动一个单位(因此,他的x或y坐标也将加1或减1)。
现在希望通过移动士兵,使得所有士兵彼此相邻的处于同一条水平线内,即所有士兵的y坐标相同并且x坐标相邻。
请你计算满足要求的情况下,所有士兵的总移动次数最少是多少。
需注意,两个或多个士兵不能占据同一个位置。

输入

第一行输入整数N,代表士兵的数量。
接下来的N行,每行输入两个整数x和y,分别代表一个士兵所在位置的x坐标和y坐标,第i行即为第i个士兵的坐标(x[i],y[i])。

输出

输出一个整数,代表所有士兵的总移动次数的最小值。

样例输入

5
1 2
2 2
1 3
3 -2
3 3

样例输出

8

提示

数据范围:1≤N≤10000,−10000≤x[i],y[i]≤10000

来源

[提交][状态]