单色路径

题目描述

有一个 $H$ 行 $W$ 列的网格,每个格子被涂成白色或黑色。

对于所有满足 $1 \le i \le H$ 且 $1 \le j \le W$ 的整数对 $(i, j)$,从上到下第 $i$ 行、从左到右第 $j$ 列的格子(简称为格子 $(i, j)$)的颜色用 $A_{i, j}$ 表示。若 $A_{i, j} = 0$ 则该格子为白色,若 $A_{i, j} = 1$ 则为黑色。

你可以任意次(可以是 $0$ 次)、以任意顺序执行以下操作:

• 选择一个整数 $i$($1 \le i \le H$),支付 $R_i$ 日元,将网格中从上到下第 $i$ 行的每个格子颜色反转(白变黑,黑变白)。
• 选择一个整数 $j$($1 \le j \le 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}$

输出格式

输出答案。

样例

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

数据范围

• $2 \le H, W \le 2000$
• $1 \le R_i \le 10^9$
• $1 \le C_j \le 10^9$
• $A_{i, j} \in \lbrace 0, 1\rbrace$
• 输入中的所有值均为整数。