问题描述

我们有一个 $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)$ 是黑色。

你可以任意次数（包括 $0$ 次）以任意顺序执行以下操作：

• 选择一个整数 $i$，使得 $1 \leq i \leq H$，支付 $R_i$ 日元（日本货币），并翻转网格中从上往下数第 $i$ 行的每个方格的颜色（白色方格变为黑色，黑色方格变为白色）。
• 选择一个整数 $j$，使得 $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$ $...$ $R_H$ $C_1$ $C_2$ $...$ $C_W$ $A_{1, 1}A_{1, 2}... A_{1, W}$ $A_{2, 1}A_{2, 2}... A_{2, W}$ $\vdots$ $A_{H, 1}A_{H, 2}... 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

现在，存在一条路径从方格 $(1, 1)$ 到方格 $(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