T454246 「2024 百度之星选拔赛」2024 幻想乡越野赛

2024年，幻想乡预计举办一场团体越野赛。 本场比赛由八云家主办，参赛队伍高手云集。 有魔理沙、爱丽丝和帕秋莉组成的“魔女组”，灵梦和八云紫组成的“结界组”（怎么主办方还有参赛的？有黑幕）等一众全明星队伍。 当然也有以琪露诺、 大妖精为首的众多妖精组成的队伍，而这只队伍的名字叫 “baka队”。 “baka队” 一共有 $n$ 名参赛成员，每个参赛成员有一个速度 $v_i$ 和一个 “baka” 值 $b_i$ （$1 \le i \le n$）。 比赛允许每个参赛队员单独行动，也允许一名队员 $i$ 与另一名参赛队员 $j$ 签订契约在一起行动，此时另一名队员 $j$ 会附着在这名参赛队员 $i$ 身上。 当队员 $i$ 和队员 $j$ 在一起行动时（队员 $j$ 附着在队员 $i$ 上），有如下两种情况： - 若队员 $i$ 的“baka”值满足 $b_i \ge b_j$，则队员 $i$ 不会受到影响，速度仍然为 $v_i$； - 若队员 $i$ 的“baka”值满足 $b_i < b_j$，则队员 $i$ 会由于队友 $j$ 太蠢，导致速度变为 $v_i - (b_j - b_i)$。 如果队员 $j$ 会导致队员 $i$ 的速度变为负数，则队员 $i$ 就不会和队员 $j$ 一起行动。 每名队员身上最多只能附着一个除了自己以外的队员，附着在其他队员身上的队员身上不能附着其他队员。 也就是说最多两个人一起行动，不能是三个人及以上。 **所有未附着在其他队员身上的队员中，最小的队员的速度**，即为 **整个队伍的速度**。 求整个队伍 **可以达到的最大速度为多少**。

**有多组测试数据** 第一行输入一个整数 $T$ $\;$ ($1 \le T \le 10^5$) ，表示测试数据组数。 对于每组测试数据： 第一行输入一个整数 $n$ $\;$ ($1\le n \le 10^5$)，表示 “baka” 队中参赛队员的数量。 接下来 $n$ 行，第 $i$ 行输入两个整数 $v_i$ 和 $b_i$ $\;$ ($1 \le v_i, b_i \le 10^9$)，分别表示第 $i$ 个队员的速度和 "baka" 值。 保证所有组测试数据满足 $\sum n \le 10^5$。

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

### 样例解释 **对于第一组测试数据** - 队员 $1$ 身上附着一个队员 $5$。由于 $b_1 > b_5$，故队员 $1$ 速度不变，仍然为 $12$。 - 队员 $3$ 身上附着一个队员 $2$。由于 $b_3 < b_2$，故队员 $3$ 的速度减少 $b_2 - b_3 = 2$，即速度变为 $10 - 2 = 8$。 - 队员 $4$ 独立行动，速度为 $9$。 因此答案为 $8$。 **对于第二组测试数据** 成员 $1$ 无法附着在任何其他队员身上，故最终整个队伍的速度为 $1$。 因此答案为 $1$。