2041: 宝典2第七章流水作业调度问题

【题目描述】流水作业调度问题(flowshop.cpp/c/pas) POJ 2751

有句谚语说如果马有投票权，世界上不会有汽车。而事实是就算马有投票权，它们还是会被汽车淘汰。正所谓生产力和科技进步的车轮是谁也无法抵挡的。魔法世界的工业生产早已实现了自动化，虽然这曾经引起长达十余年的由失业工人发动的大规模抗议浪潮。

话说逆转“时空陷”的机器就是在魔法学院的自动化生产线上完成的，已知完成Ｎ个作业要在由两台机器M₁和M₂组成的流水线上完成加工，每个作业i必须先在M₁上然后在M₂上加工，时间分别为a_i和b_i。

确定这n个作业的加工顺序，使得从第一个任务开始在M₁上加工到最后一个任务在M₂上加工完成的总时间尽量小。

【输入格式】

每组测试数据第一行有一个整数Ｎ(1 ≤ N ≤ 10000), 表示作业数，以下Ｎ行每行包含两个整数a和b (0≤a，b≤100)，表示作业在Ｍ_１和Ｍ_２上加工的时间。所有测试数据结束标志为0。

【输出格式】

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

【输入样例】

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

【输出样例】

24

23

47

28