题目描述

城市中的道路都与坐标轴平行。两个位置 $(x,y)$ 和 $(x',y')$ 之间的距离为 $|x-x'|+|y-y'|$。

平面上有 $n$ 个快递分发点，第 $i$ 个分发点的坐标为 $(x_i,y_i)$。请在平面上选择一个位置建立快递站，使快递站到所有分发点的距离之和最小，并求出这个最小值。

输入格式

第一行包含一个整数 $n$，表示快递分发点的数量。

接下来 $n$ 行，每行包含两个整数 $x_i,y_i$，表示第 $i$ 个分发点的坐标。

输出格式

输出一个整数，表示快递站到所有分发点的最小距离之和。

样例

4
1 0
0 1
-1 0
0 -1

4

样例解释

将快递站建在 $(0,0)$ 时，距离之和为 $4$。

12
-3490 -4095
-1501 -2560
-2136 -1321
1344 4010
-2299 -1926
3226 1118
-3303 -3606
3475 4710
6572 -1306
-3707 1139
-2557 -3784
-1801 -1955

55083

数据范围与提示

• $-10^4 \le x_i,y_i \le 10^4$。
• 对于 $30\%$ 的数据，$1 \le n \le 20$。
• 对于 $60\%$ 的数据，$1 \le n \le 2000$。
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$。