AT_past202109_k ニワトリのお見合い

[problemUrl]: https://atcoder.jp/contests/past202109-open/tasks/past202109_k ニワトリのオスが $ 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 $ $ 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 $

答えを整数として出力せよ。

### 注意 この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ ### Sample Explanation 1 たとえば、オス $ 1 $ とメス $ 3 $ 、オス $ 2 $ とメス $ 4 $ をつがいにする時、幸福度の総和は $ 7+6+9+3+1+8+9+6=49 $ となり、これが最適です。 ### Sample Explanation 2 $ 1 $ 組もつがいを作れない場合も、 $ 1 $ 組もつがいを作らないことが最適である場合もあります。