← 返回题目列表

AtCoder · abc437_c

F. 驯鹿和雪橇 2

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

有 N 驯鹿和一辆雪橇。的 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
  • 所有输入值均为整数。
  • 总和 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

对于第一个测试用例,如果第 3 只驯鹿拉雪橇,第 1 只和第 2 只驯鹿乘坐雪橇,则驯鹿拉雪橇的总力量为 P_3=9,骑在雪橇上的驯鹿的总重量为 W_1+W_2=7,满足条件。由于并非所有驯鹿都能乘坐雪橇,所以答案是 2.