/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
ニワトリのオスが P 羽、メスが Q 羽います。
オスには 1,2,\dots,P 、メスには 1,2,\dots,Q の番号がつけられています。
また、0 と 1 のみからなる P 行 Q 列の行列 S が与えられます。
S の上から i 行目、左から j 列目、すなわち、 S_{i,j} が 1 であるときオス i とメス j は仲が良く、 0 であるときオス i とメス j は仲が悪いです。
このもとで、仲の良いニワトリのオスとメスのペアをいくつか(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 は
0と1のみからなる P 行 Q 列の行列である - 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
1 組もつがいを作れない場合も、 1 組もつがいを作らないことが最適である場合もあります。
入力例 3
4 3 100 100 100 111 5 4 3 2 9 8 100 1 200 50 10 9 8 6
出力例 3
332
Score : 6 points
Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
There are P roosters and Q hens.
The roosters are numbered 1,2,\dots,P, and the hens are numbered 1,2,\dots,Q.
Additionally, you are given a P-by-Q matrix S consisting of 0 and 1.
If the element at the i-th from the top and j-th column from the left of S, or S_{i,j}, is 1, Rooster i and Hen j are on good terms; if S_{i,j} is 0, they are on bad terms.
Consider choosing some number (possibly zero) of pairs of a rooster and a hen on good terms to form couples. It is not allowed to include the same chicken in multiple couples, and neither is it to pair up a rooster and a hen on bad terms.
After some couples are formed, each chicken will have the following happiness.
- If Rooster i belongs to a couple, his happiness will be A_i; otherwise, his happiness will be B_i.
- If Hen i belongs to a couple, her happiness will be C_i; otherwise, her happiness will be D_i.
Find the maximum possible total happiness of the P+Q chickens, achieved by forming optimal couples.
Constraints
- P,Q,A_i,B_i,C_i,D_i are all integers.
- 1 \le P,Q \le 100
- S is a P-by-Q matrix consisting of
0and1. - 1 \le A_i,B_i,C_i,D_i \le 10^9
Input
Input is given from Standard Input in the following format:
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
Output
Print the answer as an integer.
Sample Input 1
4 4 0010 1111 0010 0010 7 4 6 1 4 9 5 3 1 1 2 8 9 4 6 5
Sample Output 1
49
If, for example, we pair Rooster 1 with Hen 3 and Rooster 2 with Hen 4, the total happiness will be 7+6+9+3+1+8+9+6=49, which is optimal.
Sample Input 2
3 4 0000 0000 0000 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Sample Output 2
56
There may be no couple to form, and it may be optimal to form no couple.
Sample Input 3
4 3 100 100 100 111 5 4 3 2 9 8 100 1 200 50 10 9 8 6
Sample Output 3
332