383. 【25CSPS提高组】社团招新 中等

小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 $n$ 个新成员，其中 $n$ 为偶数。现在小 L 希望将他们分到协会不同的部门。 算法协会共设有三个部门，其中第 $i (1 ≤ i ≤ n)$ 个新成员对第 $j (1 ≤ j ≤ 3)$ 个部门的满意度为 $a_{i,j}$。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 $i (1 ≤ i ≤ n)$ 个新成员分配到了第 $d_i ∈ \{1, 2, 3\}$ 个部门，则该分配方案的满意度为 $\sum_{i=1}^{n}a_{i,d_i}$。 小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于$\frac{n}{2}$ 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。