有n个作业(编号为1~n)要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi(1≤i≤n)。
流水作业调度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工,就不允许被中断,直到该作业被完成,即非优先调度。
输入格式:输入包含若干个用例。每个用例第一行是作业数n(1≤n≤1000),接下来n行,每行两个非负整数,第i行的两个整数分别表示在第i个作业在第一台机器和第二台机器上加工时间。以输入n=0结束。
输出格式:每个用例输出一行,表示采用最优调度所用的总时间,即从第一台机器开始到第二台机器结束的时间。
输入样例:
4
5 6
12 2
4 14
8 7
0
输出样例:
33