当前没有测试数据。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

小 L 为算法协会招收了 $n$ 个新成员，$n$ 为偶数，准备将他们分到三个部门。第 $i$ 个新成员对第 $j$ 个部门的满意度为 $a_{i,j}$。

每名新成员恰好分到一个部门，分配方案的满意度为所有成员对分配到的部门的满意度之和，即 $\sum_{i=1}^n a_{i,d_i}$，其中 $d_i\in\{1,2,3\}$。

要求没有任何一个部门被分配多于 $n/2$ 个成员。求满足要求的分配方案的最大满意度。

输入格式

本题有多组测试数据。第一行一个正整数 $t$。每组数据第一行一个正整数 $n$，随后 $n$ 行，第 $i$ 行三个非负整数 $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\le t\le5$；$2\le n\le10^5$，且 $n$ 为偶数；$0\le a_{i,j}\le2\times10^4$。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF