该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你们正在参加一项越野跑团体比赛。你们队有 $n$ 名队员，其中 $v_i$ 是 $i$ 名队员的速度， $w_i$ 是他的体重 比赛允许每位队员单独行动或背负另一位队员行动，当队员 $i$ 背着队员 $j$ 时，如果队员 $i$ 的体重大于或等于队员 $j$ 的体重，则队员 $i$ 的速度保持不变，为 $v_i$ 但是，如果成员 $i$ 的重量小于成员 $j$ 的重量，则成员 $i$ 的速度将减小，减幅为两者重量之差，变为 $v_i - (w_j - w_i)$ ，如果成员 $i$ 的速度变为负值，那么成员 $i$ 就无法搬运成员 $j$ 。
每个成员最多只能携带一名其他成员。如果一名成员被携带，他不能同时携带另一名成员，对于所有未被携带的成员，速度最慢的成员的速度就是整个团队的速度。求全队可能的最大速度

输入格式

有多个测试用例。
输入的第一行包含一个整数 $T$ ，表示测试用例的数量。对于每个测试用例
第一行包含一个整数 $n$ ( $1 \le n \le 10^5$ )，表示团队成员人数
对于下面的 $n$ 行，第$i$行包含两个整数 $v_i$ 和 $w_i$ （ $1 \le v_i, w_i \le 10^9$ ），表示第$i$名队员的速度和重量
保证所有测试用例的 $n$ 之和不超过 $10^5$

输出格式

对每个测试用例输出一行，其中包含一个整数，表示整个团队的最高速度

样例

2
5
10 5
1 102
10 100
7 4
9 50
2
1 100
10 1

8
1

第一个测试用例的最佳策略如下所示：
让成员 $1$ 携带成员 $4$ 。作为 $w_{1} > w_{4}$ ，成员 $1$ 的速度保持不变，仍然是 $10$ 。
让 $3$号成员携带 $2$ 号成员。由于 $w _{3} < w _{2}$ ，成员 $3$ 的速度将减少 $w _{2} - w _{3} = 2$ ，变为 $10 - 2 = 8$ 。
成员 $5$ 将单独行动。他的速度为 $9$
所以答案是 $8$