棋盘的中心

题目描述

国际象棋中的国王可以用一步走到周围八个格子，类似国王的走棋方法，给定两个点的坐标 $(x,y)$ 与 $(x',y')$，定义两点间的棋盘距离为：

给定二维平面上的 $n$ 个点的坐标，请在这些点中找到一个中心点，使得其他点到这个中心的棋盘距离之和最小，输出这个最小值。

输入格式

第一行：单个正整数 $n$。

第二行到第 $n+1$ 行：第 $i+1$ 行有两个整数 $x_i$ 和 $y_i$，表示一个点的坐标。

输出格式

单个自然数：表示其他点到最优中心的棋盘距离之和。

样例输入 #1

5
10 0
0 10
0 0
10 10
5 5

样例输出 #1

20

样例说明 #1

$(5,5)$ 是中心，其他点到中心的棋盘距离都是 $5$。

数据范围

• $-1000000000\le x_i,y_i\le 1000000000$；
• 对于 30% 的数据，$1\le n\le 20$；
• 对于 60% 的数据，$1\le n\le 5000$；
• 对于 100% 的数据，$1\le n\le 100000$。

测试点分布