COCI 2007/2008, Contest #6

Task CESTARINE

In a single day, N of Luka's trucks travel a specific highway. The highway has a number of exits and entrances. An exit with a particular number is in the same location as the entrance with that number.

Upon entering the highway, a truck driver receives a ticket which indicates the entrance he used. When exiting, the driver pays a toll equal to the absolute difference of the entrance and exit numbers. For example, if a ticket says he used entrance 30, then exiting at exit 12 will cost him 18.

Luka has figured out a way to save toll money that his company daily spends. Any two drivers can meet on the highway and exchange tickets, even if their routes don't overlap. Tickets can be exchanged an arbitrary number of times.

However, a driver cannot use an exit if his ticket says he used the same entrance, since that would be suspicious.

Write a program that calculates the least total amount of tolls that the drivers can achieve by exchanging tickets.

Input

The first line contains the integer N (1 ≤ N ≤ 100 000), the number of trucks.

Each of the following N lines contains two distinct integers between 1 and 1 000 000. These are in order the entrance and exit numbers of one truck.

No two trucks will use the same highway entrance or the same exit.

Output

Output the least total amount of tolls Luka's company must pay.

Note: use 64-bit integer types (long long in C/C++, int64 in Pascal).

Examples

3
3 65
45 10
60 25

32

3
5 5
6 7
8 8

5

In the first example, the first and third drivers will exchange tickets. After this, the second and third drivers exchange tickets. After this, the drivers will have the tickets 60, 3, 45, respectively. The total amount in tolls is |65−60| + |10−3| + |25−45| = 32.

All Submissions
Best Solutions

Point Value: 20
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 13, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)