알리바바

우리 어린 시절 이야기에 나오는 유명한 인물 알리바바는, 아이들에게 계속 행복을 주기 위해 불멸의 존재가 되고 싶어 한다. 그 자격을 얻으려면, 그는 여전히 특별한 일들을 해낼 수 있음을 증명해야 한다. 곧게 뻗은 길을 따라 서로 다른 위치에 $n$개의 보물($n \le 10000$)이 놓여 있다. 각 보물에는 제한 시간이 있어, 그 시간이 지나면 사라진다. 알리바바는 $n$개의 보물을 모두, 그리고 빠르게 손에 넣어야 하므로, 가장 유리한 위치에서 출발하여 각 보물이 사라지기 전에 어떤 순서로 집어야 할지를 알아내야 한다.

알리바바는 모든 보물의 위치와 제한 시간을 알고 있다. 위치 $i$는 길의 가장 왼쪽 끝으로부터 거리 $d_i$에 있으며, 알리바바는 단위 속력으로 길을 따라 움직이므로 거리 $x$를 이동하는 데 시간 $x$가 걸린다. 보물을 집는 데 걸리는 시간은 0이다. 시각 $0$에 자신이 고른 위치에서 출발할 때, 알리바바는 모든 보물을 (각각 그 제한 시간 이내에) 집을 수 있는 가장 이른 시각, 즉 마지막 보물을 집는 시각을 최소로 하고 싶어 한다.

입력은 여러 개의 데이터 집합으로 이루어지며, 각 집합은 하나의 보물 모음을 나타낸다. 각 데이터 집합은 보물의 개수 $n$으로 시작하고, 이어서 위치 제한시간 쌍이 위치의 오름차순으로 $n$개 주어진다. 수들 사이에는 공백 문자가 자유롭게 나타날 수 있다. 위치와 제한 시간은 음이 아닌 정수이며, 입력은 항상 올바르다. 입력은 파일의 끝(EOF)에서 종료된다.

각 데이터 집합에 대해, 알리바바가 모든 보물이 사라지기 전에 집을 수 있는 가장 이른 시각을 한 줄에 출력한다. 그것이 불가능하면 대신 No solution을 출력한다.