AT_abc264_f [ABC264F] Monochromatic Path

[problemUrl]: https://atcoder.jp/contests/abc264/tasks/abc264_f 各マスが白または黒で塗られた $ H $ 行 $ W $ 列のグリッドがあります。 $ 1\ \leq\ i\ \leq\ H $ かつ $ 1\ \leq\ j\ \leq\ W $ を満たす整数の組 $ (i,\ j) $ について、 グリッドの上から $ i $ 行目、左から $ j $ 行目のマス（以下、単にマス $ (i,\ j) $ と呼ぶ）の色は $ A_{i,\ j} $ で表されます。 $ A_{i,\ j}\ =\ 0 $ のときマス $ (i,\ j) $ は白色、$ A_{i,\ j}\ =\ 1 $ のときマス $ (i,\ j) $ は黒色です。 「下記の $ 2 $ つの操作のどちらかを行うこと」を好きなだけ（ $ 0 $ 回でも良い）繰り返すことができます。 - $ 1\ \leq\ i\ \leq\ H $ を満たす整数を選び、$ R_i $ 円払った後、グリッドの上から $ i $ 行目にあるそれぞれのマスの色を反転させる（白色のマスは黒色に、黒色のマスは白色に塗り替える）。 - $ 1\ \leq\ j\ \leq\ W $ を満たす整数を選び、$ C_j $ 円払った後、グリッドの左から $ j $ 列目にあるそれぞれのマスの色を反転させる。 下記の条件を満たすようにするためにかかる合計費用の最小値を出力して下さい。 - マス $ (1,\ 1) $ から「現在いるマスの右隣もしくは下隣のマスに移動する」 ことを繰り返してマス $ (H,\ W) $ まで移動する経路であって、通るマス（マス $ (1,\ 1) $ とマス $ (H,\ W) $ も含む）の色がすべて同じであるようなものが存在する。 本問題の制約下において、有限回の操作によって上記の条件を満たすようにすることが可能であることが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ R_1 $ $ R_2 $ $ \ldots $ $ R_H $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_W $ $ A_{1,\ 1}A_{1,\ 2}\ldots\ A_{1,\ W} $ $ A_{2,\ 1}A_{2,\ 2}\ldots\ A_{2,\ W} $ $ \vdots $ $ A_{H,\ 1}A_{H,\ 2}\ldots\ A_{H,\ W} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ H,\ W\ \leq\ 2000 $ - $ 1\ \leq\ R_i\ \leq\ 10^9 $ - $ 1\ \leq\ C_j\ \leq\ 10^9 $ - $ A_{i,\ j}\ \in\ \lbrace\ 0,\ 1\rbrace $ - 入力はすべて整数 ### Sample Explanation 1 白色のマスを `0` 、黒色のマスを `1` で表します。 初期状態のグリッドに対し、$ R_2\ =\ 3 $ 円払って上から $ 2 $ 行目にあるそれぞれのマスを反転させると、 ``` 0100 0100 1010 ``` となります。さらに、$ C_2\ =\ 6 $ 円払って左から $ 2 $ 列目にあるそれぞれのマスを反転させると、 ``` 0000 0000 1110 ``` となり、マス $ (1,\ 1) $ からマス $ (3,\ 4) $ への移動経路であって通るマスの色がすべて同じであるようなものが存在する状態になります（例えば $ (1,\ 1)\ \rightarrow\ (2,\ 1)\ \rightarrow\ (2,\ 2)\ \rightarrow\ (2,\ 3)\ \rightarrow\ (2,\ 4)\ \rightarrow\ (3,\ 4) $ という経路）。 かかった合計費用は $ 3+6\ =\ 9 $ 円であり、このときが考えられる中で最小です。