/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
この問題の問題設定は F 問題と一部共通しています。
2222 年の CatCoder では、CatCoder Double Contest（以下、C2C と略します）を開催することになりました。
いま、問題案を持っている writer が N 人います。 各 writer の問題案は難易度によって Hard, Medium, Easy の 3 種類に分類されており、i 人目の writer が持っている Hard, Medium, Easy の問題案の個数はそれぞれ A_i,B_i,C_i です。
各 C2C では Div.1, Div.2 の 2 部門を同時に 1 つずつ開催します。それぞれの部門の開催に必要な問題案は以下の通りです。
- Div.1：同じ writer の Hard, Medium の問題案を 1 つずつ
- Div.2：同じ writer の Medium, Easy の問題案を 1 つずつ
ここで、Div.1, Div.2 の writer は必ずしも同じである必要がない点に注意して下さい。 また、各問題案は高々 1 回の C2C の 1 つの部門にしか使用出来ません。
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 行目には i 番目のテストケースについて、C2C を開催出来る回数としてありうる最大値を出力せよ。
入力例 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
1 つ目のテストケースについて、以下のように問題案を使用することにより、C2C を 2 回開催出来ます。
| Div.1 | Div.2 | |
|---|---|---|
| 第 1 回 | 1 人目の writer の Hard, Medium | 2 人目の writer の Medium, Easy |
| 第 2 回 | 2 人目の writer の Hard, Medium | 2 人目の writer の Medium, Easy |
Score : 500 points
Problem Statement
The problem setting of this problem is partially shared with Problem F.
In the year 2222, CatCoder will hold the CatCoder Double Contest (abbreviated as C2C).
There are N writers who have problem proposals. Each writer's problem proposals are classified into 3 types by difficulty: Hard, Medium, Easy, and the i-th writer has A_i, B_i, C_i problem proposals of Hard, Medium, Easy, respectively.
Each C2C simultaneously holds 2 divisions, Div.1 and Div.2. The problem proposals required for each division are as follows:
- Div.1: One Hard and one Medium problem proposal from the same writer
- Div.2: One Medium and one Easy problem proposal from the same writer
Note that the writers for Div.1 and Div.2 do not necessarily have to be the same. Also, each problem proposal can be used in at most one division of one C2C.
Find the maximum number of times C2C can be held.
T test cases are given, so find the answer for each.
Constraints
- 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
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
Output
Output T lines.
The i-th line should contain the maximum number of times C2C can be held for the i-th test case.
Sample Input 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
Sample Output 1
2 0 7 2500000000 998830769
For the first test case, C2C can be held 2 times by using problem proposals as follows:
| Div.1 | Div.2 | |
|---|---|---|
| 1st time | Hard, Medium from the 1st writer | Medium, Easy from the 2nd writer |
| 2nd time | Hard, Medium from the 2nd writer | Medium, Easy from the 2nd writer |