题目描述

$Bob$ 考入 Tsinghua 了，军训结束后要进行“团队越野赛”。

$Bob$ 所在的团队有 $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$ ，表示队员人数。

接下来 $n$ 行, 每行两个整数 $v_i$ 和 $w_i$ ,表示队员的速度和体重。

输出格式

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

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

8
1

样例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$。

对于第二组测试样例：第二名队员无法背起第一名队员，因此团队速度就是 $1$

下发样例：down

数据规模与约定

所有数据满足：

$1 \leq t \leq 10, 1\leq n \leq 10^5, 1\leq v_i,w_i \leq 10^9$

保证所有组数据中 $\sum n \leq 10^5$