题目背景

CSP-S 2025 T1

题目描述

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

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

小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于n/2个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。

输入格式

从文件club.in中读入数据。 本题包含多组测试数据。 输入的第一行包含一个正整数t，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： •第一行包含一个正整数n，表示新成员的数量。 •第i+1(1≤i≤n)行包含三个非负整数a(i,1),a(i,2),a(i,3)，分别表示第i个新成员对第1,2,3个部门的满意度。

输出格式

输出到文件club.out中。 对于每组测试数据，输出一行一个非负整数，表示满足小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，均不超过4/2=2，满意度为4+4+5+5=18。

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

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

说明/提示

【样例2】 见选手目录下的club/club2.in与club/club2.ans。 该样例满足测试点3,4的约束条件。 【样例3】 见选手目录下的club/club3.in与club/club3.ans。 该样例满足测试点5∼8的约束条件。 【样例4】 见选手目录下的club/club4.in与club/club4.ans。 该样例满足测试点9的约束条件。 【样例5】 见选手目录下的club/club5.in 与 club/club5.ans。 该样例满足测试点15,16的约束条件。

【数据范围】 对于所有测试数据，保证： • 1≤t≤5； • 2≤n≤10⁵，且n为偶数； • 对于所有1≤i≤n，1≤j≤3，均有0≤a(i,j)≤2×10⁴。

特殊性质A：对于所有1≤i≤n，均有a(i,2)=a(i,3)=0。 特殊性质B：对于所有1≤i≤n，均有a(i,3)=0。 特殊性质C：对于所有1≤i≤n，1≤j≤3，a(i,j)均在[0,2×10⁴]中独立均匀随机生成