|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
There are parcels that must be delivered. Each parcel has its own starting and destination points. Each parcel must be delivered from the starting point to the destination point and each parcel is uniform. There is one delivery man called Jim. Jim can carry at most one parcel at a time. During delivery, he does NOT drop the parcel he is carrying on his way. Also after delivering all the parcels, Jim must return back to his starting position. Jim wants to minimize the moving distances. Assume that all the parcel information is given before Jim starts to move. The information of each parcel is just composed of starting point and destination point. The city that Jim works consists of just one straight road. The leftmost position of the road is the starting point of Jim and each parcel’s starting and destination points lie on the road. Jim delivers all the parcels alone.
Let’s see an example above. There are two parcels, one to be delivered from 1 to 4 , and the other from 3 to 6. 0 denotes the starting point of Jim. The other numbers denote distances from 0 to the corressponding points. The following figure indicates an optimal solution. In the optimal solution, Jim first moves to 4 delivering the parcel at 1 to 4. Then Jim moves back to position 3. Jim delivers the parcel at 3 to 6. Finally, Jim moves back to his starting point 0. So the total distance that he moves is 4+1+3+6=14 in this case. This is optimal for this example.
Your program is to read from standard input. The input consists of T test cases. The number of test cases T (1 ≤ T ≤ 20) is given in the first line of the input. At the first line of each test case, a positive integer A (1 ≤ A ≤ 50,000) which denotes the number of parcels, is given. At the second line of each test case, two positive integers B (1 ≤ B ≤ 100,000) and C (1 ≤ C ≤ 100,000) for each parcel, are given in one line. B and C denote the starting and the destination points of a parcel, respectively.
Your program is to write to standard output. For each test case, print the minimum moving distance of Jim for the test case in a line.
2 2 1 4 3 6 2 1 2 3 4