练习专区

Jacky下定决心要考研了，天天跑图书馆去自习。图书馆管理员老师发现，每个考研的学生都有各自喜爱的一些自习位置，如果能尽量让每个学生在自己喜爱的位置自习，学习及考研的效果会大大增强。为了避免学生哄抢座位，管理员老师决定合理安排一下每个学生的自习位置。规则如下： （1）首先将图书馆自习室划分成N个不同的区域。（例如文史区，外语区，数学区，哲学区，理工区等） （2）每个学生对不同的区域有不同的喜好程度（喜好程度度的范围为 1 -100 的整数，喜好程度越大表示该学生越希望被安排到相应的区域学习） （3）由于每个区域可以容纳的学生数量有限，管理员老师希望找到一个最优的调整方案令到总的喜好程度最大。 输入 第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个学生。 第二行是 N 个整数构成的数列 a ，其中 a[i] 表示第 i 个区域可以容纳的学生数， (1<=a[i]<=M ， a[1]+a[2]+..+a[N]=M) 。 紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个学生对第 j 个区域的喜好度。 输出 对于每个测试数据，输出可以达到的最大的喜好程度。 样例输入 3 3 1 1 1 100 50 25 100 50 25 100 50 25 样例输出 175

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个学生。 第二行是 N 个整数构成的数列 a ，其中 a[i] 表示第 i 个区域可以容纳的学生数， (1<=a[i]<=M ， a[1]+a[2]+..+a[N]=M) 。 紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个学生对第 j 个区域的喜好度。

对于每个测试数据，输出可以达到的最大的喜好程度。

3 3
1 1 1
100 50 25
100 50 25
100 50 25

175