将 $n$ 名成员分到三个部门，其中 $n$ 为偶数。第 $i$ 人分到第 $j$ 个部门可获得满意度 $a_{i,j}$。

每人必须且只能进入一个部门，每个部门的人数至多为 $n/2$，部门可以为空。求总满意度的最大值。

输入格式

第一行一个整数 $T$，表示测试数据组数。

每组数据的第一行包含一个偶数 $n$。随后给出 $n$ 行，每行包含三个满意度值 $a_{i,1},a_{i,2},a_{i,3}$。

输出格式

对每组数据输出一行一个整数，表示最大总满意度。

样例 1

3
4
4 2 1
3 2 4
5 3 4
3 5 1
4
0 1 0
0 1 0
0 2 0
0 2 0
2
10 9 8
4 0 0

18
4
13

数据范围与原题特殊限制

对于所有测试数据，保证：

• $1 \leq t \leq 5$;
• $2 \leq n \leq 10^5$，且 $n$ 为偶数;
• 对于所有 $1 \leq i \leq n$，$1 \leq j \leq 3$，均有 $0 \leq a_{i,j} \leq 2 \times 10^4$。

特殊性质 A：对于所有 $1 \leq i \leq n$，均有 $a_{i,2} = a_{i,3} = 0$。

特殊性质 B：对于所有 $1 \leq i \leq n$，均有 $a_{i,3} = 0$。

特殊性质 C：对于所有 $1 \leq i \leq n$，$1 \leq j \leq 3$，$a_{i,j}$ 均在 $[0, 2 \times 10^4]$ 中独立均匀随机生成。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。