当前没有测试数据。

F - 单色路径

给定一个有 $H$ 行和 $W$ 列的网格。每个方格都被涂成白色或者黑色。 对于每对整数 $(i, j)$ 满足 $1 \leq i \leq H$ 并且 $1 \leq j \leq W$， 第 $i$ 行从上往下数第 $j$ 列（我们用 Square $(i, j)$ 来表示这个方格）的颜色用 $A_{i, j}$ 表示。 如果 $A_{i, j} = 0$，则 Square $(i, j)$ 是白色，如果 $A_{i, j} = 1$，则 Square $(i, j)$ 是黑色。

你可以按照任意顺序任意多次进行以下操作：

• 选择一个整数 $i$，满足 $1 \leq i \leq H$，支付 $R_i$ 日元，并翻转网格中第 $i$ 行方格的颜色。（白色变黑色，黑色变白色）
• 选择一个整数 $j$，满足 $1 \leq j \leq W$，支付 $C_j$ 日元，并翻转网格中第 $j$ 列方格的颜色。

输出满足以下条件的最小总成本：

• 存在一条从 Square $(1, 1)$ 到 Square $(H, W)$ 的路径，可以通过向下或者向右移动重复来获得，该路径上的所有方格（包括 Square $(1, 1)$ 和 Square $(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}$

输出

输出答案。

输入样例1

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

输出样例1

9

我们用 0 表示白色方格，1 表示黑色方格。 在初始网格中，你可以支付 $R_2 = 3$ 日元来翻转网格中第 2 行的每个方格的颜色，使网格变成：

0100
0100
1010

然后，你可以支付 $C_2 = 6$ 日元来翻转网格中第 2 列的每个方格的颜色，使网格变成：

0000
0000
1110

现在，存在一条从 Square $(1, 1)$ 到 Square $(3, 4)$ 的路径，该路径上的所有方格都具有相同的颜色（如路径 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$）。 所支付的总成本是 $3+6 = 9$ 日元，这是最小可能的成本。

输入样例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