U529035 座位

> 教室明窗净几处，读书声朗心自舒。 14 班刚刚结束了一场重要的期末考试。按照班级的传统，考试结束后，座位会根据同学们的考试成绩和其他因素重新安排。\ 小 P 作为班长，被老 R 要求设计一个公平合理的座位方案。

假定 14 班共有 $n$ 名同学。他们的学号是从 $1$ 到 $n$。\ 所有 $r$ 行 $c$ 列的座位都分布于一个矩形区域内。 老 R 关心班级整体利益，给出了亿些**座位安排规则**： - 每个座位只能安排一名同学。 - 座位安排需要综合考虑**考试成绩**和**日常表现**。 - 考试成绩占总评分的 $60\%$，日常表现占 $40\%$。每位同学最终都会得到一个**综合**评分 ${s_i}$。 小 P 考虑到个人利益：每个同学对班级中的不同座位可能有不同的偏好。调查发现： - 每位同学对座位的偏好不同，用一个矩阵 $a_{i,j}$ 表示，其中 $a_{i,j}$ 表示同学 $i$ 对第 $j$ 个座位的偏好值（偏好值越高，越喜欢该座位）。 - 每个座位的偏好值由老 R 根据教室的环境因素提前设定。 早在老 G 统治时期，14 班就推行了**座位限制规则**： - 座位的安排需要根据综合评分进行优先级排序，评分越高的同学可以优先选择座位。 - 每个座位只能安排一名同学，且每位同学只能选择一个座位。 - 老 R 出于人道主义要求，希望尽量满足每位同学的座位偏好。 小 P 需要合理安排每个同学的座位。应同时满足以下条件： - 根据综合评分的优先级安排座位。 - 尽量满足每位同学的座位偏好。 - 最大化所有同学的总偏好值。

第一行包含三个整数 $n$、$r$ 和 $c$，分别表示班级人数、座位的行数和列数。 第二行包含 $n$ 个整数 $s_1$，$s_2$，……，$s_n$，表示每位同学的综合评分。 接下来 $r$ 行，每行包含 $c$ 个整数 $a_{i,j}$，表示每个座位的偏好值。

输出一个整数，表示在满足所有条件的情况下，所有同学的总偏好值的最大值。

##### 数据范围： - $2 ≤ n ≤ 50$ - $1 ≤ r, c ≤ 10$ - $1 ≤ s_i ≤ 100$ - $1 ≤ a_{i,j} ≤ 100$ --- ##### 数据的解释： 教室有 $2$ 行 $3$ 列的座位，总共有 $6$ 个座位。 同学 1 的综合评分为 $85$，同学 2 为 $90$，同学 3 为 $75$，同学 4 为 $80$。 座位的偏好值如下： ``` 10 20 30 40 50 60 ``` 一个可能的座位安排是： - 同学 2 选择座位 $(2,\ 3)$，偏好值为 $60$。 - 同学 1 选择座位 $(2,\ 2)$，偏好值为 $50$。 - 同学 4 选择座位 $(2,\ 1)$，偏好值为 $40$。 - 同学 3 选择座位 $(1,\ 3)$，偏好值为 $30$。 总偏好值为 $60 + 50 + 40 + 30 = 180$。 ##### 说明 此题为 AI 出的，小 P 改的。仅供参考。