← 返回题目列表

AtCoder · past202109_k

K. 新婚快乐!

中文机器翻译题面 查看原题

分数: 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