P3964 [TJOI2013] Squirrel Gathering

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$.

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 a single integer, the minimum possible sum of distances the squirrels need to travel to gather.

### 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