P9559 [SDCPC 2023] Fast and Fat

您正在参加一场团体越野比赛。您的队伍共有 $n$ 名队员，其中第 $i$ 名队员的速度为 $v_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$。

每组数据输出一个整数，表示整个队伍可以达到的最大速度。 **【样例解释】** 样例数据的最优策略如下： - 队员 $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$。

The optimal strategy for the sample test case is shown as follows: - Let member $1$ carry member $4$. As $w_1 > w_4$, member $1$'s speed remains unchanged, which is still $10$. - Let member $3$ carry member $2$. As $w_3 < w_2$, member $3$'s speed will decrease by $w_2 - w_3 = 2$ and becomes $10 - 2 = 8$. - Member $5$ shall move alone. His/Her speed is $9$. So the answer is $8$.