配点 : $500$ 点

問題文

各マスが白または黒で塗られた $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)$ も含む）の色がすべて同じであるようなものが存在する。

本問題の制約下において、有限回の操作によって上記の条件を満たすようにすることが可能であることが証明できます。

制約

• $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$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$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}$

出力

答えを出力せよ。

3 4
4 3 5
2 6 7 4
0100
1011
1010

9

白色のマスを 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$ 円であり、このときが考えられる中で最小です。

15 20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78
39 97 12 53 62 32 38 84 49 93 53 26 13 25 2 76 32 42 34 18
01011100110000001111
10101111100010011000
11011000011010001010
00010100011111010100
11111001101010001011
01111001100101011100
10010000001110101110
01001011100100101000
11001000100101011000
01110000111011100101
00111110111110011111
10101111111011101101
11000011000111111001
00011101011110001101
01010000000001000000

125