题目描述

航天飞机“奋进号”（Endeavour为英式拼写，Endeavor为美式拼写。为什么NASA使用英式拼写？答案可通过百度或谷歌搜索）正面临危险！

奋进号遇到了与2003年哥伦比亚号相同的问题。当其被送入太空时，航天飞机表面的部分材料受损。重返大气层时，高温空气可能摧毁航天飞机并使其解体。NASA表示，拯救奋进号的唯一方法是派遣另一架航天飞机前往太空协助维修。但考虑到现有航天飞机（如亚特兰蒂斯号和发现号）的状况，科学家认为它们无法完成这一高要求任务。NASA必须建造一架新的航天飞机。

这架新航天飞机有$N$个部件需要制造。由于航天飞机将在所有部件准备就绪后组装，NASA希望最小化所有部件的制造时间。

有两个车间$S1$和$S2$。每个部件必须按顺序在这两个车间加工，即先在$S1$加工，然后在$S2$加工。已知一个车间不能同时加工多个部件。你的任务是计算制造所有部件的最短时间。

输入格式

输入包含多个测试块。每个测试块的第一行是一个整数$N$（$1 \leq N \leq 10000$），表示部件数量。接下来的$N$行，每行包含两个整数$a$和$b$（$0 \leq a, b \leq 100$），分别表示该部件在$S1$和$S2$的加工时间。

最后一个测试块后是一个单独的$0$，无需处理。

输出格式

每个测试块输出一行，即最早完成时间。

示例输入与输出

输入数据 1

4
1 2
3 4
5 6
7 8
4
10 1 
10 1 
1 10
1 10
5
4 5
4 1
30 4
6 30
2 3
6
5 7
1 2
8 2
5 4
3 7
4 4
0

输出数据 1

24
23
47
28

来源

POJ Monthly--2006.01.22, anonymous