题目描述

在一个奇幻的森林里，住着一位勇敢的小精灵。森林中有很多神奇的宝物散落在不同的地方，每一件宝物都有一个消失的时间，必须在宝物消失之前及时收集。小精灵的任务是从自己喜欢的任意点出发，收集所有的宝物。每一件宝物的位置和消失的时间都已经知道，但她需要找到一个最佳的收集顺序，确保能够在所有宝物消失之前都收集完。

她有一张地图，地图上标出了每个宝物的位置和最后的时间限期。她的目标是找到一条路径，使得她能够最早的完成所有宝物的收集，确保每件宝物在其限期之前被收集完。如果她不能按照某种顺序收集所有宝物，那么就无法完成任务。

为了帮助小精灵，你需要编写程序来找到她的最短完成时间，或者判断是否有可行的收集顺序。如果没有方案，输出No solution。

输入

每个测试用例首先给出一个整数 $n$，表示宝物的数量（$n \leq 10000$）。接着是 $n$ 个宝物的位置和消失时间的配对 $(d_i, t_i)$，其中 $d_i$ 表示宝物的位置（与森林左端的距离），$t_i$ 表示该宝物的消失时间。所有宝物按位置从左到右排列。

输出

对于每个测试用例，输出一个整数，表示最短的时间，即小精灵能在所有宝物消失之前完成收集的最小时间。如果不可能收集所有宝物，输出No solution。

样例

5  
1 3  
3 1  
5 8  
8 19  
10 15  
5  
1 5  
2 1  
3 4  
4 2  
5 3

11
No solution