1906_算法设计例题：流水作业调度（DP）

n个作业 { 1, 2, …, n } 要在由两台机器M₁和M₂组成的流水线上完成加工。每个作业加工的顺序都是先在M₁上加工，然后在M₂上加工。M₁和M₂加工作业i所需的时间分别为a_i和b_i，1 ≤ i ≤ n。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M₁上开始加工，到最后一个作业在机器M₂上加工完成所需的时间最少。

输入的第一行为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是作业数n（ 1 ≤ n ≤ 100 ），接下来n行，每行两个正整数a_i和b_i，分别表示第i件作业在M₁和M₂上加工所需的时间。

对应每个测试样例输出一行，只有一个整数，表示完成所有作业所需时间的最小值。

2
2
3 5
2 3
3
3 5
2 3
1 1

10
11