#P0823. Are you sure?

Are you sure?

题目描述

你们正在参加一项越野跑团体比赛。你们队有 nn 名队员,其中第 ii 名队员的速度是viv_i , 体重是wiw_i。

比赛允许每位队员单独行动或背负另一位队员行动。

当队员 ii 背着队员 jj 时:

  • 如果队员 ii 的体重大于或等于队员 jj 的体重,则队员 ii 的速度保持不变,为 viv_i。
  • 如果队员 ii 的体重小于队员 jj 的体重,则队员 ii 的速度将减少,减幅为两者体重之差,变为 vi−(wj−wi)v_i - (w_j - w_i)。
  • 如果vi−(wj−wi)≤0v_i - (w_j - w_i) \le 0,那么成员 ii 就无法搬运成员 jj。

每名成员最多只能携带一名其他成员。如果一名成员被携带,他不能同时携带另一名成员。

对于所有未被携带的成员,速度最慢的成员的速度就是整个团队的速度。

求全队可能的最大速度。

输入格式

本题含有多组测试数据。

第一行输入一个正整数T(1≤T≤1000)T(1 \le T \le 1000),表示测试用例数量。

接下来对于每组测试数据,第一行输入一个整数n(1≤n≤105)n(1 \le n \le 10^5),表示团队成员人数。

接下来 nn 行,每行输入两个整数 viv_i 和 wi (1≤vi,wi≤109)w_i\ (1 \le v_i, w_i \le 10^9),表示第 ii 名队员的速度和重量。

题目保证:在单个测试文件中∑n≤105\sum n \le 10^5。

输出格式

对于每组测试用例,输出一行一个整数,表示整个团队可能的最大速度。

样例

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

提示

样例的第一个测试用例的最佳策略如下:

让成员 11 携带成员 44。由于 w1>w4w_1 > w_4,成员 11 的速度保持不变,仍然是 1010。

让成员 33 携带成员 22。由于 w3<w2w_3 < w_2,成员 33 的速度将减少 w2−w3=2w_2 - w_3 = 2,变为 10−2=810 - 2 = 8。

成员 55 将单独行动,他的速度为 99。

因此答案是 88。