时间限制： 1.0 秒

空间限制： 512 MB

题目描述

理发店同时来了 $n$ 名顾客，你作为理发店的店长，需要为每名顾客先洗发再剪发。已知服务第 $i$ 名顾客洗发需要 $a_i$ 分钟，剪发需要 $b_i$ 分钟。

你需要遵循如下限制 :

• 由于人手有限，同时只有最多一位顾客在洗发；同样地，同时只有至多一位顾客在剪发。
• 对于某一位顾客，必须在洗发结束后才能开始剪发。

另外，由于这些顾客都是同时来的，你可以按照任意顺序为他们服务，没有先来后到的区别。请求出完成所有服务的最少时间。

输入格式

从标准输入读入数据。

一个输入文件中会包含多个输入数据。输入文件的第一行为一个正整数 $T$，表示输入数据的组数。

每个输入数据的第一行包含一个整数 $n$，表示顾客的数量。接下来 $n$ 行，每行包含两个正整数 $a_i$ 和 $b_i$，表示第 $i$ 位顾客洗发和剪发所需的时间。

输出格式

输出到标准输出。

输出 $T$ 行，每行包含一个整数，表示你对该输入数据求出的最少时间。

2
3
10 20
25 40
20 30
3
30 35
25 25
25 30

100
115

样例 1 解释

对于第一个输入数据，一种可能的最优方案如下：

• 0 分钟到 10 分钟，为第 1 位顾客洗发；
• 10 分钟到 30 分钟，为第 3 位顾客洗发；
• 10 分钟到 30 分钟，为第 1 位顾客剪发；
• 31 分钟到 56 分钟，为第 2 位顾客洗发；
• 30 分钟到 60 分钟，为第 3 位顾客剪发；
• 60 分钟到 100 分钟，为第 2 位顾客剪发。

对于第二个输入数据，一种可能的最优方案如下：

• 0 分钟到 25 分钟，为第 2 位顾客洗发；
• 25 分钟到 50 分钟，为第 2 位顾客剪发；
• 25 分钟到 50 分钟，为第 3 位顾客洗发；
• 50 分钟到 80 分钟，为第 3 位顾客剪发；
• 50 分钟到 80 分钟，为第 1 位顾客洗发；
• 80 分钟到 115 分钟，为第 1 位顾客剪发。

子任务

本题共有 $10$ 个测试点，每个测试点 $10$ 分。对于所有输入数据，保证 $1\le T\le 100$，每个数据的 $0\le n\le 5$，且 $1\le a_i, b_i\le 100$。