[COCI2007-2008#6] CESTARINE

题目描述

Luka 的 $n$ 辆卡车行驶在一辆高速路上。高速路上有许多出入口。我们认为相同编号的出入口在同一位置。 开进高速路后,司机会收到一张写着他入口号的单子。驶出时,驾驶员支付的通行费等于出入口号的绝对差。 Luka 是一个爱贪小便宜的人。他发现,即使他们的路线不重叠,司机们可以在高速路上交换他们的单子。 但是,不能再同一位置的出入口进行上高速与下高速。 请你编程求出最少的通行费。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3
3 65
45 10
60 25 

输出样例 #1

32

输入样例 #2

3
5 5
6 7
8 8 

输出样例 #2

5

说明

#### 样例 #1 解释 最少的通行费为 $ |65−60| + |10−3| + |25−45| = 32$。 #### 数据规模及约定 对于 $100\%$ 的数据,$1 \le n \le 10^5$,$1 \le x, y \le 10^6$,$x \not= y$。 #### 提示 请使用 $64$ 位整数类型(在 C / C++ 语言中为 `long long`,在 Pascal 语言中为 `int64`),否则可能会导致答案错误(即 Wrong Answer)。 #### 说明 - 本题满分 $80$ 分。 - 本题默认开启 O2 优化开关。 - 题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T6 CESTARINE,译者 @[tearing](https://www.luogu.com.cn/user/219791)。