题目描述

有一些大城市的道路，都是相互平行或垂直的，所以在城市间行走，不能用两点间的欧几里得距离计算长度，而是应该使用曼哈顿距离计算长度。两点间的曼哈顿距离定义如下：设两点的坐标分别为 (x,y) 与  (x′,y′)，它们之间的曼哈顿距离定义为

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

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

输入格式

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

输出格式

单个自然数：表示最优中心到各个点的曼哈顿距离之和。

数据范围

−5000≤xi,yi≤5000；

对于 30% 的数据，1≤n≤20；

对于 60% 的数据，1≤n≤2000；

对于 100% 的数据，1≤n≤100000；

样例数据

输入:

4

1 0

0 1

-1 0

0 -1

输出:

4

说明:

最优中心应该设置在(0,0)处