题目描述

平面上有 \(n\) 个油井，现在要建立一条主干线，用来把所有的油井产出的原油都输送出去，主干线是平行于 \(x\) 轴的一条直线，每个油井通过一条支线把原油输送到主干线上，现在给定 \(n\) 个油井在平面上的坐标，那么应该把主干线建在什么地方才能让所有的支干线的总长度最小呢？编程计算所有的支干线的总长度。

格式

输入格式

第一行为正整数 \(n(≤2×10^6)\)，接下来 \(n\) 行，每行两个正整数 \((x,y)\)，表示油井的坐标，\(x,y\) 均小于 \(10^6\)。

输出格式

输出仅一个整数，表示所有支干线的总长度。

样例1

输入样例1

2
0 0
10 10

输出样例1

10

限制

\(30\%\) 的数据，\(n≤10^5\);

\(70\%\) 的数据，\(n≤8×10^5\);

\(100\%\) 的数据，\(n≤2×10^6\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("pipe.in","r",stdin);
freopen("pipe.out","w",stdout);