题目描述

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

max{∣x−x ′ ∣,∣y−y ′ ∣}

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

输入格式

第一行：单个正整数 n。

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

输出格式

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

数据范围

−1,000,000,000≤x i ​ ,y i ​ ≤1,000,000,000；

1≤n≤100,000；

样例数据

输入:

5

10 0

0 10

0 0

10 10

5 5

输出:

20

说明: (5,5)是中心，其他点到中心的棋盘距离都是5