← 返回题目列表

AtCoder · arc201_a

A. CatCoder 双人大赛

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

分数: 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第二位作家