Given a list of coordinates x1, x2, ..... xn, and each of coordinates has a value time t1, t2, ... tn. U can start at anywhere in the ox axis, u have to find the smallest time to reach all the points x1, x2... xn, and u also have to reach every points in the time of that point, meaning that assume at time t u reach xk point, so t<=tk. Output the smallest time or "No solution".

please help me this problem xD P/s: link this problem :D Your text to link here...

Hello everyone!, today i want to ask u about how to solve this problem, i have been trying to solve but it really hard for me i think! XD please help me! XDXDXD (https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4507)

Alibaba the famous character of our childho o d stories would like to b e immortal in order to keep bringing happiness to children. In order to rich 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 lo cated 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 b efore their deadlines starting from the most favorable p osition. 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 program input is from a text file. Each data set in the file 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. 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’.

Sample Input

5

1 3

3 1

5 8

8 19

10 15

5

1 5

2 1

3 4

4 2

5 3

Sample Output

11

No solution