ALIBB  Alibaba
Alibaba the famous character of our childhood stories would like to be immortal in order to keep bringing happiness to children. In order to reach this status he needs to prove that he is still able to do some unusual things. There are n treasures, (n <= 10000) each in a different place located along a straight road. Each treasure has a time limit, after that it vanishes. Alibaba must take all the n treasures, and he must do it quickly. So he needs to figure out the order in which he should take the treasures before their deadlines starting from the most favorable position. Alibaba has the list of places and deadlines of the treasures. A place i is located at distance d_{i} from the leftmost end of the road. The time it takes to take a treasure is instantaneous.
Alibaba must find the smallest time by which he can take all the treasures.
Input
The first line of the input contains an integer K <= 10  determining the number of datasets
Each data set in the input stands for a particular set of treasures. For each set of treasures the input contains the number of treasures, and the list of pairs place  deadline in increasing order of the locations. White spaces can occur freely between the numbers in the input.The input data are correct.
Output
For each set of data the program prints the result to the standard output on a separate line. The solution is represented by the smallest time by which Alibaba can take all the treasures before they vanish. If this is not possible then the output is "No solution".
Example
Input: 2 5 1 3 3 1 5 8 8 19 10 15 5 1 5 2 1 3 4 4 2 5 3 Output: 11 No solution
hide comments
Aditya Muraletharan:
20130622 14:19:27
If a treasure has a deadline d, it can be collected at any time t < d, but not at t = d.


Alex Abbas:
20130301 08:57:57
I fail to understand the problem 
Added by:  ThanhVy Hua 
Date:  20050129 
Time limit:  0.652s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  ACM South Eastern European Region 2004 