题目描述

POJ 2751

有句谚语说如果马有投票权,世界上不会有汽车。而事实是就算马有投票权,它们还是 会被汽车淘汰。正所谓生产力和科技进步的车轮是谁也无法抵挡的。魔法世界的工业生产 早已实现了自动化,虽然这曾经引起长达十余年的由失业工人发动的大规模抗议浪潮。 话说逆转“时空陷”的机器就是在魔法学院的自动化生产线上完成的,已知完成$\red{N}$个作 业要在由两台机器$\red{M1}$和$\red{M2}$组成的流水线上完成加工,每个作业$\red{i}$必须先在$\red{M1}$上然后在 $\red{M2}$上加工,时间分别为$\red{ai}$和$\red{bi}$. 确定这$\red{n}$个作业的加工顺序,使得从第一个任务开始在$\red{M1}$上加工到最后一个任务在 $\red{M2}$上加工完成的总时间尽量小。

输入格式

每组测试数据第一行有一个整数$\red{N(1≤N≤10 000)}$,表示作业数,以下$\red{N}$行每行包， 含两个整数$\red{a}$和$\red{b(0≤a,b≤100)}$,表示作业在$\red{M1}$和$\red{M2}$上加工的时间。所有测试数据 结束标志为$\red{0}$。

输出格式

每组测试数据输出--行最少完成时间。

样例

输入样例

4
1 2
3 4
5 6
7 8
4
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

输出样例

24
23
47
28