题目描述 理发店同时来了 $n$ 名顾客，你作为理发店的店长，需要为每名顾客先洗发再剪发。已知服务第 $i$ 名顾客洗发需要 $a i$ 分钟，剪发需要 $b i$ 分钟。 你需要遵循如下限制： 由于人手有限，同时只有最多一位顾客在洗发；同样地，同时只有至多一位顾客在剪发 对于某一位顾客，必须在洗发结束后才能开始剪发。 另外，由于这些顾客都是同时来的，你可以按照任意顺序为他们服务，没有先来后到的区别。请求出完成所有服务的最少时间。 输入格式 从标准输入读入数据。 一个输入文件中会包含多个输入数据。输入文件的第一行为一个正整数 $T$，表示输入数据的组数。 每个输入数据的第一行包含一个整数 $n$，表示顾客的数量。接下来 $n$ 行，每行包含两个正整数 $a i$ 和 $b i$，表示第 $i$ 位顾客洗发和剪发所需的时间。 输出格式 输出到标准输出。 输出 $T$ 行，每行包含一个整数，表示你对该输入数据求出的最少时间。 数据范围 对于所有输入数据，保证 $1 \leq T \leq 100$，每个数据的 $0 \leq n \leq 5$，且 $1 \leq a i, b i \leq 100$。 输入样例1 2 3 10 20 25 40 20 30 3 30 35 25 25 25 30 输出样例1 100 115