拙いものと思えども、
その手に握る其れこそが、
いつか幻想を生んでいく。
虽然尚显笨拙,
但此刻他们手握之物,
终有一日,会将幻想孕育。
——童遊 めらみぽっぷ
问题描述
一天,幻想乡内的少女们决定去参加八云紫的宴会。
她们分散在一个很大很大的方阵上。且每位少女都在格点上。由于紫有隙间,因此只要少女们聚集到一个点上,紫就可以把她们全部接走啦。
因此,少女们想让你算出她们聚集到同一个点的最短距离和。
注意:少女们只能沿着方阵的网格走,不可滑翔、瞬移、开摩托横冲直撞等。
输入格式
第一行是一个整数 $n$ ,代表有多少位少女。
下来 $n$ 行一行两个整数 $x$ 与 $y$ ,代表每位少女的横坐标与纵坐标。
输出格式
一个整数,是你给出的答案。
样例一
input
4 1 1 2 3 4 6 8 10
output
21
explanation
如图所示,其中红点代表少女,绿点代表聚集到一起的点,黑边代表走的路径。
数据范围与约定
对于 $30\%$ 的数据,保证所有的纵坐标都相等,$n \leq 100$。
对于另外 $20\%$ 的数据,保证每一位少女的横坐标等于她的纵坐标,$n \leq 100$。
对于上述 $50\%$ 的数据,保证所有少女横纵坐标均在 $[1,800]$ 内。
对于 $100\%$ 的数据,若有 $i < j$ ,则保证,$x_i \leq x_j $ ,$y_i \leq y_j$。$n \leq 100000$。
保证所有少女横纵坐标均在$[1,100000]$内。少女可能重叠。
时间限制: $1\mathrm{s}$
内存限制: $256\mathrm{MB}$
下载
ex_aso1.in/out 对应样例。
ex_aso2.in/out 对应 $50\%$ 的数据范围。
ex_aso3.in/out 对应 $100\%$ 的数据范围。