说明

有n个机器零件${J_1，J_2，…，J_n}$，每个零件必须先由机器1处理，再由机器2处理。零件Ji需要机器1、机器2的处理时间为$t_{1i}、t_{2i}$。如何安排零件加工顺序，使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成，所需的总加工时间最短？

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。

每组测试数据第一行输入机器零件个数n（1<=n<=20）。

接下来有n行，每行输入两个数，代表第一台机器上的加工时间和第二台机器上的加工时间$t_{1i}、t_{2i}（1<=t_{1i}、t_{2i}<=100）$。

输出格式

对于每一组输入，输出最短机器零件加工时间。

每组的输出占一行。

样例

2
6
5 7
1 2
8 2
5 4
3 7
4 4
7
3 7
8 2
10 6
12 18
6 3
9 10
15 4

28
65

来源

《趣学算法》5.6节