84426 - CESTARINE

Luka 的 n 辆卡车行驶在一辆高速路上。高速路上有许多出入口。我们认为相同编号的出入口在同一位置。

开进高速路后,司机会收到一张写着他入口号的单子。驶出时,驾驶员支付的通行费等于出入口号的绝对差。

Luka 是一个爱贪小便宜的人。他发现,即使他们的路线不重叠,司机们可以在高速路上交换他们的单子。

但是,不能再同一位置的出入口进行上高速与下高速。

请你编程求出最少的通行费。

输入

第一行,一个正整数 n,表示卡车的个数。

接下来,n 行,每行两个正整数,x_i, y_i, 表示入口和出口的编号。

保证不会有任何两辆卡车使用相同的入口编号,也不会有任何两辆卡车使用相同的出口编号。

输出

第一行,一个正整数 ans,表示最少的通行费。

样例

输入

3
3 65
45 10
60 25 

输出

32

输入

3
5 5
6 7
8 8 

输出

5

提示

样例 #1 解释

最少的通行费为 |65−60| + |10−3| + |25−45| = 32

数据规模及约定

对于 100\% 的数据,1 \le n \le 10^51 \le x, y \le 10^6x \not= y

来源

COCI2007-2008 #6

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题