题目描述

大城市的道路是相互平行或垂直的，如果在城市的道路上行走，不能用点与点之间的直线距离计算长度，而是应该定义两个点（设坐标分别为 (x,y)与 (x',y')）的城市距离为

|x-x'|+|y-y'|

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

输入格式

第一行：单个正整数 n。 第二行到第 n+1 行：第 i+1 行有两个整数 xi 和 yi，表示一个点的坐标。

输出格式

单个整数：表示各点到中心的距离之和的最小值。

样例数据

4
1 0
0 1
-1 0
0 -1

4

数据范围

• $-5000 \leq xi,yi \leq 5000$
• 对于 30% 的数据，$1 \le n \le 20$；
• 对于 60% 的数据，$1 \le n \le 2000$；
• 对于 100% 的数据，$1 \le n \le 100000$；