Boys and Girls#11810
There are types of boys and 2 \cdot n girls. The types of boys are numbered with integers from to , while the girls are numbered with integers from to 2 \cdot n.
There are c_i boys of the -th type, and each of them likes girls numbered a_i and b_i.
Find the size of the largest set of boys such that for every pair of boys in this set, there is at least one girl that both of them like.
In this problem, each test contains several sets of input data. You need to solve the problem independently for each such set.
The first line contains one integer (1 \le T \le 500) — the number of sets of input data. The description of the input data sets follows.
In the first line of each input data set, there is one integer (1 \le n \le 7 \cdot 10^5).
In the next lines, there are three integers a_i, b_i, c_i (1 \le a_i < b_i \le 2 \cdot n, 1 \le c_i \le 10^9) — the parameters for the corresponding type of boys.
It is guaranteed that a_i \ne a_j or b_i \ne b_j for any 1 \le i < j \le n.
It is guaranteed that the sum of across all input data sets of a single test does not exceed 7 \cdot 10^5.
For each set of input data, output one integer on a separate line — the size of the largest set of boys such that for every pair of boys in this set, there is at least one girl that both of them like.
Example 1
Let be the sum of over all test case input sets of one test, and be the sum of all c_i over all test case input sets of one test.
( points): n \le 5;
( points): S \le 100;
( points): each girl is liked by boys of no more than two types;
( points): S \le 3000;
( points): S \le 3 \cdot 10^5;
( points): K \le 10^7;
( points): with no additional constraints.