P7194 [COCI 2007/2008 #6] CESTARINE

Luka’s $n$ trucks are driving on a highway. There are many entrances and exits on the highway. We consider entrances/exits with the same number to be at the same location. After entering the highway, a driver receives a slip of paper with their entrance number written on it. When leaving, the toll the driver pays is equal to the absolute difference between the entrance number and the exit number. Luka is someone who likes to take advantage of small savings. He发现 that even if their routes do not overlap, drivers can exchange their slips on the highway. However, entering and exiting cannot happen at entrances/exits that are at the same location. Please write a program to find the minimum total toll.

The first line contains a positive integer $n$, the number of trucks. The next $n$ lines each contain two positive integers $x_i, y_i$, representing the entrance number and the exit number.

The first line contains a positive integer $ans$, the minimum total toll.

#### Sample #1 Explanation The minimum total toll is $ |65−60| + |10−3| + |25−45| = 32$. #### Constraints For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le x, y \le 10^6$, $x \not= y$. #### Hint Please use a $64$-bit integer type (in C / C++ it is `long long`, in Pascal it is `int64`), otherwise the answer may be wrong (i.e., Wrong Answer). #### Notes - This problem is worth $80$ points in total. - This problem enables the O2 optimization switch by default. - Translated from [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T6 CESTARINE, translator @[tearing](https://www.luogu.com.cn/user/219791). Translated by ChatGPT 5