Cow Highway (highway.X)
FR's N (1 <= N <= 100,000) cows are each making trips on the highway. The
highway has several stops, where each stop is the location of an entrance
and an exit. Each cow has a particular route it needs to take; cow i wishes
to enter the highway at A_i and exit at B_i (1 <= A_i, B_i <= 1,000,000,000).
No two cows will have either the same entrances or the same exits.
Rising prices have prompted the government to charge drivers. In
particular, upon entering the highway each cow is given a ticket stating
the entrance used. When the cow leaves the highway at location Y with a
ticket containing the number X, she must pay a fee of |X - Y|.
The cows have realized that by exchanging entrance cards, they may be able
to reduce their total cost. However, they do not want a cow to have the
same location for her entrance card and exit, since that would arouse
suspicion. Thus, the cows would like you to help them determine the lowest
possible total cost while keeping entrances and exits distinct.
PROBLEM NAME: highway
INPUT FORMAT:
* Line 1: The single integer N.
* Lines 2..N+1: Line i+1 contains the two space-separated integers A_i
and B_i.
SAMPLE INPUT:
3
5 5
6 7
8 8
INPUT DETAILS:
There are 3 cows: the first cow is entering and exiting at location 5; the
second cow is entering at location 6 and exiting at location 7; the third
cow is entering and exiting at location 8.
OUTPUT FORMAT:
* Line 1: A single integer representing the minimum possible total
cost for the cows.
SAMPLE OUTPUT:
5
OUTPUT DETAILS:
Swap entrance cards so that the first cow has the card with 6, the second
cow has the card with 8, and the third cow has the card with 5. The total
cost is then |6 - 5| + |8 - 7| + |5 - 8| = 1 + 1 + 3 = 5.