分数: 6 点
警告
2021 年 10 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
有 P 公鸡和 Q 母鸡。
公鸡已编号 1,2,\dots,P,母鸡编号 1,2,\dots,Q.
此外,您还获得了 P-by-Q 矩阵 S 组成 0 和 1.
如果元素位于 i从上往下数第 j从左边数第 S,或 S_{i,j}是 1, 公鸡 i 和母鸡 j 关系良好;如果 S_{i,j} is 0,他们关系不好。
考虑选择一些(可能是零)对关系良好的公鸡和母鸡来结对。不允许多对同一只鸡,也不允许公鸡和母鸡关系不好。
一些情侣组成后,每只鸡都会有以下幸福。
- 如果公鸡 i 属于情侣,他的幸福将会是 A_i;不然他的幸福就是 B_i.
- 如果母鸡 i 属于情侣,她的幸福将会是 C_i;不然她的幸福就是 D_i.
找出最大可能的总幸福感 P+Q 鸡,通过形成最佳配对而实现。
约束
- P,Q,A_i,B_i,C_i,D_i 均为整数。
- 1 \le P,Q \le 100
- S 是 P-by-Q 矩阵组成
0和1. - 1 \le A_i,B_i,C_i,D_i \le 10^9
输入
输入由标准输入按以下格式给出:
P Q
S_{1,1}S_{1,2} \dots S_{1,Q}
S_{2,1}S_{2,2} \dots S_{2,Q}
\vdots
S_{P,1}S_{P,2} \dots S_{P,Q}
A_1 B_1
A_2 B_2
\dots
A_P B_P
C_1 D_1
C_2 D_2
\dots
C_Q D_Q
输出
将答案打印为整数。
样本输入 1
4 4 0010 1111 0010 0010 7 4 6 1 4 9 5 3 1 1 2 8 9 4 6 5
示例输出 1
49
例如,如果我们将公鸡配对 1 与母鸡 3 和公鸡 2 与母鸡 4,总的幸福将是 7+6+9+3+1+8+9+6=49,这是最佳的。
示例输入 2
3 4 0000 0000 0000 1 2 3 4 5 6 7 8 9 10 11 12 13 14
示例输出 2
56
可能没有配对,并且最好不配对。
示例输入 3
4 3 100 100 100 111 5 4 3 2 9 8 100 1 200 50 10 9 8 6
示例输出 3
332