题目描述

婷婷所在的村庄的道路都是相互平行或垂直，所以在村庄中两户居民之间的道路距离是曼哈顿距离。假设村庄两户居民的地址分别为 (x,y) 和 (x′,y′)，他们两户之间的距离为 $|x-x′|$+$|y-y′|$。

已知村庄有 n 户居民，每一户居民居住的地址为 ($x_i$,$y_i$)，保证所有居民的居住地址互不相同。现在需要建立一个快递服务站，要求快递服务站到村里各户居民的距离之和最小，请你帮助婷婷选择最合适的地址，快递服务站的地址可以和居民居住地址相同。

输入格式

第一行一个整数 n；

接下来 n 行，每行两个整数 $x_i$,$y_i$。

输出格式

一行一个整数，表示快递服务站到村里各户居民的距离之和的最小值。

4
2 0
-2 0
0 2
0 -2

8

2
0 0
0 1

1

3
0 0
3 0
0 4

7

1
10000 10000

0

提示

样例 1 解释，最优的位置应该选在 (0,0)，距离之和最小为 8。

数据范围

对于 40% 的数据：$1\le n\le 400$，$1\le x_i,y_i\le 400$。

对于 100% 的数据：$1\le n\le 10^{5}$，$-10^{4}\le x_i,y_i\le 10^{4}$，保证所有居民的居住地址互不相同