Problem Description

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.

Input Format

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.

Output Format

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

3
3 65
45 10
60 25 

32

3
5 5
6 7
8 8 

5

Hint

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 CONTEST #6 T6 CESTARINE, translator
  https://www.luogu.com.cn/user/219791

Translated by ChatGPT 5