5344: Happy Farm 5快乐农场 5
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：4
通过：3
题目描述
C. Happy Farm 5
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
For that a young pla
The new game is launched for different devices, including mobile phones. That's why the developers decided to quit using the arithmetics with the floating decimal point and use only the arithmetics of integers. The cows and the shepherd in the game are represented as points on the plane with integer coordinates. The playing time is modeled by the turns. During every turn the shepherd can either stay where he stands or step in one of eight directions: horizontally, vertically, or diagonally. As the coordinates should always remain integer, then the length of a horizontal and vertical step is equal to 1, and the length of a diagonal step is equal to
. The cows do not move. You have to minimize the number of moves the shepherd needs to run round the whole herd.
快乐农场5的创作者决定发明牛放牧的机制。游戏中的奶牛非常缓慢，移动非常缓慢，甚至可以认为它们是静止不动的。然而，食肉动物应该总是被赶走。
为此，一位年轻的球员瓦夏决定让牧羊人沿着一条封闭的小路绕着奶牛跑。奶牛严格留在路径限制的区域内非常重要，否则有些奶牛迟早会被吃掉。为了绝对确保奶牛的安全，Vasya 希望路径完成时间最短。
新游戏针对不同的设备推出，包括手机。这就是为什么开发人员决定停止使用带有浮点小数点的算术，而只使用整数的算术。游戏中的奶牛和牧羊人表示为平面上具有整数坐标的点。播放时间由转弯建模。在每一个转弯处，牧羊人可以呆在他站立的地方，也可以向八个方向之一走：水平、垂直或对角线。由于坐标应始终保持整数，因此水平和垂直步长的长度等于 1，对角线步长的长度等于。奶牛不动。你必须尽量减少牧羊人在整个牛群中奔跑所需的移动次数。
Input
The first line contains an integer N which represents the number of cows in the herd (1≤N≤105). Each of the next N lines contains two integers Xi and Yi which represent the coordinates of one cow of (|Xi|,|Yi|≤106). Several cows can stand on one point.
Output
Print the single number − the minimum number of moves in the sought path.
Examples
Input
4 1 1 5 1 5 3 1 3
Output
16
Note
Picture for the example test: The coordinate grid is painted grey, the coordinates axes are painted black, the cows are painted red and the sought route is painted green. 
输入样例 复制
输出样例 复制