Alibaba

Alibaba, the famous character from our childhood stories, would like to become immortal so that he can keep bringing happiness to children. To earn this, he must prove that he can still do some unusual things. There are $n$ treasures ($n \le 10000$), each lying in a different place along a straight road. Each treasure has a time limit, after which it vanishes. Alibaba must collect all $n$ treasures, and he must do it quickly, so he needs to work out the order in which to collect them before their deadlines, starting from the most favorable position.

Alibaba knows the places and deadlines of all treasures. Place $i$ is located at distance $d_i$ from the leftmost end of the road, and Alibaba moves along the road at unit speed, so travelling a distance of $x$ takes time $x$. Taking a treasure is instantaneous. Starting at time $0$ from a position of his choice, Alibaba wants the smallest time at which the last treasure is taken, with every treasure taken no later than its own deadline.

The input contains several data sets, each describing one set of treasures. A data set consists of the number of treasures $n$, followed by the $n$ pairs 'place deadline', given in increasing order of the places. White space may occur freely between the numbers. The places and deadlines are non-negative integers, and the input is correct. The input terminates at end of file.

For each data set, print the result on its own line: the smallest time by which Alibaba can collect all the treasures before they vanish. If this is impossible, print No solution instead.