HIGHWAY  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
On the first line of the input is the integer T (1 ≤ T ≤ 5), the number of test cases. T cases follow, each beginning with the single integer N (2 ≤ N ≤ 100,000). Each of the next N lines contains two integers between 1 and 1,000,000,000 inclusive, representing the entrance and exit numbers of a truck. Note that no two trucks will have the same entrance or exit numbers.
Output
For each test case, output the least total amount of tolls Luka's company must pay.
Example
Input: 2 3 3 65 45 10 60 25 3 5 5 6 7 8 8 Output: 32 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.
Warning: large input/output data.hide comments
pranjal_27:
20171025 20:56:01
I have tried my best to solve this question but yet getting no idea about it . Please can someone mail me its solution . thanks in advance . my mail address : p.gupta.pranjal.140003@gmail.com


1528459:
20141212 18:20:43
Can you give me some input/output? Thank you 
Added by:  Neal Wu 
Date:  20081113 
Time limit:  1s1.111s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  Croatian Open 07/08  Contest 6 