← 返回题目列表

AtCoder · abc264_f

I. 单色路径

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个网格 H 行和 W 列。 每个方块都被漆成白色或黑色。 对于每个整数对 (i, j) 这样 1 \leq i \leq H 和 1 \leq j \leq W, 正方形的颜色 i从顶部算起的第行和 j从左边算起第 1 列(我们简单地用 Square 表示这个方格) (i, j)) 表示为 A_{i, j}。 广场 (i, j) 为白色,如果 A_{i, j} = 0,如果 A_{i, j} = 1.

您可以执行任意数量的以下操作(可能是 0) 次(任意顺序):

  • 选择一个整数 i 这样 1 \leq i \leq H,支付 R_i 日元(日本的货币),并反转每个方块的颜色 i- 网格中从顶部算起的第行。 (白色方块涂成黑色,黑色方块涂成白色。)
  • 选择一个整数 j 这样 1 \leq j \leq W,支付 C_j 日元,并反转每个方块的颜色 j- 网格中从左侧算起的第列。

打印满足以下条件的最小总成本:

  • 存在一条从 Square 出发的路径 (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 \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- 从顶部开始的第 1 行来制作网格:

0100
0100
1010

然后,您可以支付 C_2 = 6 日元反转每个方块的颜色 2- 从左起第 3 行来制作网格:

0000
0000
1110

现在,存在一条从 Square 出发的路径 (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