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

负重前行

题目描述

Y 同学和他的 $N-1$ 个伙伴，共 $N$ 人，组成了一支队伍参加团队越野赛。每个队员 $i$ 都有两个属性：速度 $v_i$ 和体重 $w_i$。

比赛规则允许一名队员背起另一名队员前行。具体规则如下：

1. 一个队员至多可以背负一名其他队员。
2. 被背负的队员不能再背负别人。
3. 当队员 $i$ 背负队员 $j$ 时，他们的组合速度（即队员 $i$ 的新速度）取决于两人的体重：
   • 如果 $w_i \ge w_j$，队员 $i$ 的力量足以轻松承担，其速度保持为 $v_i$ 不变。
   • 如果 $w_i < w_j$，队员 $i$ 会感到吃力，其速度将减少，变为 $v_i - (w_j - w_i)$。
   • 特别地，如果减速后的速度将小于等于 $0$（即 $v_i - (w_j - w_i) \le 0$），则队员 $i$ 无法背起队员 $j$。

队伍中所有没有被背负的队员（即独立行走或背着别人的队员）构成“行进组”。整个队伍的行进速度，由“行进组”中速度最慢的队员决定。

Y 同学需要制定一个最优的背负方案（即决定谁背谁，谁独立行走），以最大化整个队伍的行进速度。请你计算这个最大速度。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $N$，表示队员的数量。 接下来 $N$ 行，每行包含两个整数 $v_i, w_i$，分别表示第 $i$ 名队员的速度和体重。

输出格式

对于每组测试数据，输出一行一个整数，表示队伍可能达到的最大行进速度。

样例

样例输入 #1

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

样例输出 #1

8
1

提示

样例 1 解释

对于第一组测试数据，队员信息按输入顺序编号为 1 至 5。 一种最优策略如下：

• 队员 1（速度 $10$，体重 $5$）背负队员 4（速度 $7$，体重 $4$）。由于 $w_1 \ge w_4$，队员 1 的速度不变，仍为 $10$。
• 队员 3（速度 $10$，体重 $100$）背负队员 2（速度 $1$，体重 $102$）。由于 $w_3 < w_2$，队员 3 的速度变为 $v_3 - (w_2 - w_3) = 10 - (102 - 100) = 8$。
• 队员 5（速度 $9$，体重 $50$）独立行走，速度为 $9$。

此时，“行进组”的成员为队员 1、3、5，他们的速度分别为 $10, 8, 9$。 队伍的行进速度为 $\min(10, 8, 9) = 8$。可以证明这是能达到的最大速度。

对于第二组测试数据，队员 1（$v=1, w=100$），队员 2（$v=10, w=1$）。

• 方案一：两人都独立行走。行进组为 {队员1, 队员2}，速度为 $\min(1, 10)=1$。
• 方案二：队员 1 背负队员 2。由于 $w_1 > w_2$，可行。行进组为 {队员1}，速度为 $v_1=1$。
• 方案三：队员 2 背负队员 1。由于 $w_2 < w_1$，速度将变为 $v_2-(w_1-w_2) = 10 - (100-1) = -89 \le 0$。此方案不可行。

综上，最大速度为 $1$。

数据范围与约定

对于所有测试数据，保证：

• $1 \le N \le 10^5$。
• $1 \le v_i, w_i \le 10^9$。
• 所有测试数据的 $N$ 之和不超过 $10^5$（$\sum N \le 10^5$）。