题目描述

各マスが白または黒で塗られた $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}$

输出格式

答えを出力せよ。

题目大意

在 $n\times m$ （$1 \leq n,m \leq 2000$）的网格图中，每个格子有 $0,1$ 两种，有两种操作：

• 将第 $i$ 行元素全部异或 $1$，花费 $r_i$ 代价。
• 将第 $j$ 列元素全部异或 $1$，花费 $c_j$ 代价。

进行若干次上述操作后，使得图中存在一条从 $(1, 1)$ 到 $(n, m)$ 的路径（只能向下或向右走），路径上的颜色相同。

求最小代价。

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

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

提示

制約

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