分数: 500 点
问题陈述
本题的问题设置与问题F部分共享。
今年 2222,CatCoder将举办CatCoder双人大赛(简称C2C)。
有 N 有问题建议的作家。 每个作者的问题提案分为 3 按难度类型:困难、中等、简单和 i第作者有 A_i, B_i, C_i 分别为困难、中等、简单的问题建议。
每个C2C同时持有 2 部门,Div.1 和 Div.2。各部门所需的问题建议如下:
- Div.1:来自同一作者的一个困难和一个中等问题提案
- Div.2:来自同一作者的一份中等问题和一份简单问题提案
请注意 Div.1 和 Div.2 的作者不一定必须相同。 另外,每个问题提案最多可以在一个C2C的一个部门中使用。
求C2C可以举行的最大次数。
T 给出了测试用例,因此请找到每个测试用例的答案。
约束
- 1 \le T \le 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le A_i,B_i,C_i \le 10^9
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
输出
输出 T 行。
的 i第行应包含 C2C 可以持有的最大次数 i- 第一个测试用例。
样本输入 1
5 2 3 1 4 1 5 3 1 1 1 1 3 5 7 5 1 11 99 3 1 2 5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 6 835549144 866512240 105679868 473233032 625162103 823002638 125467290 37501686 380787083 8043910 721085797 254272563 97327826 744196952 18713225 978152989 90127986 33086297
示例输出 1
2 0 7 2500000000 998830769
第一个测试用例,可以举行C2C 2 次使用问题建议如下:
| 第 1 区 | 第 2 区 | |
|---|---|---|
| 1第一时间 | 硬,中等 1st 作家 | 中等,容易从 2第二位作家 |
| 2第 次 | 硬,中等 2第二位作家 | 中等,容易从 2第二位作家 |