问题 A: [CSP-S 2025] 社团招新

小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 $n$ 个新成员，其中 $n$ 为偶数。现在小 L 希望将他们分到协会不同的部门。

算法协会共设有三个部门，其中第 $i$ ($1\le i\le n$) 个新成员对第 $j$ ($1\le j\le 3$) 个部门的满意度为 $a_{i,j}$。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 $i$ ($1\le i\le n$) 个新成员分配到了第 $d_i\in \{1,2,3\}$ 个部门，则该分配方案的满意度为 ${\sum }_{i=1}^n{a}_{i,d_i}$。

小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 $\frac{n}{2}$

 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大

说明/提示

【数据范围】

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

• $1\le t\le 5$;
• $2\le n\le 10^5$，且 $n$ 为偶数;
• 对于所有 $1\le i\le n$，$1\le j\le 3$，均有 0≤ai,j≤2×104
  
  

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

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

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

本题包含多组测试数据。

输入的第一行包含一个正整数 $t$，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 $n$，表示新成员的数量。
• 第 $i+1$ ($1\le i\le n$) 行包含三个非负整数 $a_{i,1},a_{i,2},a_{i,3}$，分别表示第 $i$ 个新成员对第 $1,2,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
样例输出1：
18
4
13