题目描述 小 $L$ 是学校算法协会的成员。 在今年的学校社团招新中，小 $L$ 一共招收了 $n$ 个新成员，其中 $n$ 为 偶数 。 现在小 $L$ 希望将他们分到协会不同的部门。 算法协会共设有三个部门，其中第 $i (1 ≤ i ≤ n)$ 个新成员对第 $j (1 ≤ j ≤ 3)$ 个部门的满意度为 $a {i,j}$。 定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 $i (1 ≤ i ≤ n)$ 个新成员分配到了第 $d i \in \{1, 2, 3\}$ 个部门，则该分配方案的满意度为 $\sum {i=1}^n a {i,d i}$。 小 $L$ 不希望某一个部门的新成员数量过多。 具体地，他要求在分配方案中， 不存在 一个部门被分配 多于 $\frac n2$ 个新成员。 你需要帮助小 $L$ 求出，满足他要求的分配方案的满意度的最大值。 输入格式 本题包含多组测试数据。 输入的第一行包含一个正整数 $t$，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： 输出格式 对于每组测试数据，输出一行一个非负整数，表示满足小 $L$ 要求的分配方案的满意度的最大值。 数据范围 对于所有测试数据，保证： 特殊性质 $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^4]$ 中 独立均匀随机 生成。 输入样例 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