题目描述

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

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

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

求最小代价。

输入格式

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

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

9

样例 #2

样例输入 #2

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

样例输出 #2

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$
• 输入都是整数