[TJOI2013]松鼠聚会

题目描述

草原上住着一群小松鼠,每个小松鼠都有一个家。时间长了,大家觉得应该聚一聚。但是草原非常大,松鼠们都很头疼应该在谁家聚会才最合理。 每个小松鼠的家可以用一个点 $(x,y)$ 表示,两个点的距离定义为点 $(x,y)$ 和它周围的 $8$ 个点 $(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)$ 距离为 $1$。

输入输出格式

输入格式


第一行是一个整数 $N$,表示有多少只松鼠。接下来 $N$ 行,第 $i$ 行是两个整数 $x$ 和 $y$,表示松鼠 $i$ 的家的坐标。

输出格式


一个整数,表示松鼠为了聚会走的路程和最小是多少。

输入输出样例

输入样例 #1

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

输出样例 #1

20

输入样例 #2

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

输出样例 #2

15

说明

### 样例解释 在第一个样例中,松鼠在第二只松鼠家 $(-1,-2)$ 聚会;在第二个样例中,松鼠在第一只松鼠家 $(0,0)$ 聚会。 ### 数据范围 - $30\%$ 的数据,$0\le N \le 1000$; - $100\%$的数据,$0\le N \le 10^5$,$-10^9 \le x$ $y \le 10^9$。