负责人

• SleepingCup

题目描述

小 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 求出，满足他要求的分配方案的满意度的最大值。

输入格式

本题包含多组测试数据。

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

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

• 第一行包含一个正整数 $n$，表示新成员的数量。
• 第 $i+1\ (1 \le i \le n)$ 行包含三个非负整数 $a_{i,1}, a_{i,2}, a_{i,3}$，分别表示第 $i$ 个新成员对第 $1,2,3$ 个部门的满意度。

输出格式

对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意度的最大值。

样例

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 解释

该样例共包含三组测试数据。

对于第一组测试数据，可以将四个新成员分别分配到第 $1,3,1,2$ 个部门，则三个部门的新成员数量分别为 $2,1,1$，均不超过 $\frac{4}{2} = 2$，满意度为 $4 + 4 + 5 + 5 = 18$。

对于第二组测试数据，可以将四个新成员分别分配到第 $1,1,2,2$ 个部门，则三个部门的新成员数量分别为 $2,2,0$，均不超过 $\frac{4}{2} = 2$，满意度为 $0 + 0 + 2 + 2 = 4$。

对于第三组测试数据，可以将两个新成员分别分配到第 $2,1$ 个部门，则三个部门的新成员数量分别为 $1,1,0$，均不超过 $\frac{2}{2} = 1$，满意度为 $9 + 4 = 13$。

样例 2

见选手目录下的 club/club2.in 与 club/club2.ans。

该样例满足测试点 $3,4$ 的约束条件。

样例 3

见选手目录下的 club/club3.in 与 club/club3.ans。

该样例满足测试点 $5 \sim 8$ 的约束条件。

样例 4

见选手目录下的 club/club4.in 与 club/club4.ans。

该样例满足测试点 $9$ 的约束条件。

样例 5

见选手目录下的 club/club5.in 与 club/club5.ans。

该样例满足测试点 $15,16$ 的约束条件。

数据范围

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

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

特殊性质 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]$ 中独立均匀随机生成。