Description

A group of little squirrels lives on the prairie, and each squirrel has a home. After a long time, they feel they should have a gathering. However, the prairie is very large, and they are troubled about whose home would be the most reasonable place to meet.

Each squirrel’s home is represented by a point $(x,y)$. The distance between two points is defined so that the distance between point $(x,y)$ and each of its eight neighbors $(x-1,y)$, $(x+1,y)$, $(x,y-1)$, $(x,y+1)$, $(x-1,y+1)$, $(x-1,y-1)$, $(x+1,y+1)$, $(x+1,y-1)$ is $1$.

Input Format

The first line contains an integer $N$, the number of squirrels. The next $N$ lines, the $i$-th line contains two integers $x$ and $y$, the coordinates of squirrel $i$’s home.

Output Format

Output a single integer, the minimum possible sum of distances the squirrels need to travel to gather.

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

20

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

15

Hint

Sample Explanation

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

Constraints

• For $30\%$ of the testdata, $0 \le N \le 1000$.
• For $100\%$ of the testdata, $0 \le N \le 10^5$, $-10^9 \le x, y \le 10^9$.

Translated by ChatGPT 5