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

承重分组

题目描述

给定 $N$ 个个体，第 $i$ 个个体有两个属性：重量 $W_i$ 与力量 $P_i$。

你需要将每个个体分到两类之一：

支撑组：其力量会被计入总支撑力；

负载组：其重量会被计入总负载。

分组后必须满足约束： 支撑组的力量总和必须大于或等于负载组的体重总和

请你在满足约束的前提下，最大化负载组的人数 $|B|$，并输出其最大可能值。

你需要处理 $T$ 组测试数据，分别求解。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行输入一个整数 $N$；

接下来 $N$ 行，每行输入两个整数 $W_i, P_i$，表示第 $i$ 个个体的重量与力量。

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

输入输出样例 #1

输入 #1

3
3
3 1
4 1
5 9
5
1000000000 1
1000000000 1
1000000000 1
1000000000 1
1000000000 1
10
133180711 458704923
531424946 225863856
141986070 637075158
500770732 289806469
502866767 408857335
559714289 569084545
287444582 992432993
559747907 753133304
432846188 949871298
727072164 756020367

输出 #1

2
0
6

说明/提示

$1\le T\le 10^5$

$1\le N\le 3\times 10^5$

$1\le W_i, P_i\le 10^9$

单个输入文件中所有测试用例的 $N$ 之和不超过 $3\times 10^5$

样例解释：

1. 第 1 组：$N=3$，个体为 $(W_i,P_i)$：

   • $(3,1)$，$(4,1)$，$(5,9)$

   取支撑组 $A=\{3\}$，负载组 $B=\{1,2\}$，则：

   $\sum_{i\in A}P_i = 9,$ $\qquad \sum_{i\in B}W_i = 3+4=7,$

   满足 $9\ge 7$，且 $|B|=2$。
   由于不可能让 $|B|=3$（否则左侧为 $0$，右侧为总重量），因此答案为 $2$。

2. 第 2 组：$N=5$，每个个体均为 $(10^9,1)$。

   若将任意一个个体放入负载组，则右侧至少为 $10^9$，而左侧最多为 $4$（其余 4 个在支撑组时的总力量），必然不满足约束。
   因此只能令 $B=\varnothing$，答案为 $0$。