/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
N 匹のトナカイと 1 個のソリがあります。i 番目のトナカイは重さが W_i で力は P_i です。
各トナカイについて、「ソリを引く」または「ソリに乗る」のいずれかを選びます。 ただし、ソリを引くトナカイの力の総和が、ソリに乗るトナカイの重さの総和以上でなければなりません。 最大で何匹トナカイをソリに乗せることができますか？
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\leq T\leq 10^5
- 1\leq N\leq 3\times 10^5
- 1\leq W_i,P_i\leq 10^9
- 入力は全て整数
- 1 つの入力ファイルに含まれる N の総和は 3\times 10^5 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N W_1 P_1 W_2 P_2 \vdots W_N P_N
出力
T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。
入力例 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 つ目のテストケースについて、3 番目のトナカイがソリを引き、1 番目と 2 番目のトナカイがソリに乗ると、ソリを引くトナカイの力の総和は P_3=9、ソリに乗るトナカイの重さの総和は W_1+W_2=7 となるため条件を満たします。すべてのトナカイがソリに乗ることはできないため、求める答えは 2 です。
Score : 350 points
Problem Statement
There are N reindeer and one sled. The i-th reindeer has weight W_i and strength P_i.
For each reindeer, choose either "pull the sled" or "ride on the sled". Here, the total strength of the reindeer pulling the sled must be greater than or equal to the total weight of the reindeer riding on the sled. What is the maximum number of reindeer that can ride on the sled?
You are given T test cases. Solve each of them.
Constraints
- 1\leq T\leq 10^5
- 1\leq N\leq 3\times 10^5
- 1\leq W_i,P_i\leq 10^9
- All input values are integers.
- The sum of N in one input file is at most 3\times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N W_1 P_1 W_2 P_2 \vdots W_N P_N
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 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
Sample Output 1
2 0 6
For the 1st test case, if the 3rd reindeer pulls the sled and the 1st and 2nd reindeer ride on the sled, the total strength of the reindeer pulling the sled is P_3=9, and the total weight of the reindeer riding on the sled is W_1+W_2=7, satisfying the condition. Since not all reindeer can ride on the sled, the answer is 2.