A6509 | [CSP-S 2025] 社团招新

样例 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$。

数据范围

对于所有测试数据，保证：
- $1 \leq t \leq 5$；
- $2 \leq n \leq 10^5$，且 $n$ 为偶数；
- 对于所有 $1 \leq i \leq n$，$1 \leq j \leq 3$，均有 $0 \leq a_{i,j} \leq 2 \times 10^4$。



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

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

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