Problem Description

In the grasslands, there lives a group of small squirrels, each with their own home. Over time, they decided that they should gather together. However, the grasslands are vast, and the squirrels are puzzled about where the gathering should take place to be most reasonable.

Each squirrel's home can be represented by a point \((x, y)\). The distance between two points is defined as the distance from point \((x, y)\) to its eight surrounding points \((x-1, y)\), \((x+1, y)\), \((x, y-1)\), \((x, y+1)\), \((x-1, y+1)\), \((x-1, y-1)\), \((x+1, y+1)\), and \((x+1, y-1)\), which is \(1\).

Input Format

The first line contains an integer \(N\), representing the number of squirrels. The next \(N\) lines each contain two integers \(x\) and \(y\), representing the coordinates of squirrel \(i\)'s home.

Output Format

An integer representing the minimum total distance the squirrels need to travel for the gathering.

Sample Input and Output

Input Sample #1

6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2

Output Sample #1

20

Input Sample #2

6
0 0
2 0
-5 -2
2 -2
-1 2
4 0

Output Sample #2

15

Notes

Sample Explanation

In the first sample, the squirrels gather at the home of the second squirrel \((-1, -2)\); in the second sample, they gather at the home of the first squirrel \((0, 0)\).

Data Range

• \(30\%\) of the data, \(0 \le N \le 1000\);
• \(100\%\) of the data, \(0 \le N \le 10^5\), \(-10^9 \le x, y \le 10^9\).

见题面 Input 部分

见题面 Output 部分