AT_abc264_f [ABC264F] Monochromatic Path

有一个 $H$ 行 $W$ 列的网格，每个格子被涂成白色或黑色。对于满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数对 $(i, j)$，网格从上到下第 $i$ 行、从左到右第 $j$ 列的格子的颜色用 $A_{i, j}$ 表示。当 $A_{i, j} = 0$ 时，格子 $(i, j)$ 是白色；当 $A_{i, j} = 1$ 时，格子 $(i, j)$ 是黑色。 你可以任意次（也可以一次都不做）重复以下两种操作中的任意一种： - 选择一个满足 $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}$

请输出答案。

## 约束 - $2 \leq H, W \leq 2000$ - $1 \leq R_i \leq 10^9$ - $1 \leq C_j \leq 10^9$ - $A_{i, j} \in \{0, 1\}$ - 输入均为整数 ## 样例解释 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$ 日元，这是所有可能方案中的最小值。 由 ChatGPT 4.1 翻译