/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
各マスが白または黒で塗られた 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) は黒色です。
「下記の 2 つの操作のどちらかを行うこと」を好きなだけ（ 0 回でも良い）繰り返すことができます。
- 1 \leq i \leq H を満たす整数を選び、R_i 円払った後、グリッドの上から i 行目にあるそれぞれのマスの色を反転させる（白色のマスは黒色に、黒色のマスは白色に塗り替える）。
- 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 \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
となり、マス (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
Score : 500 points
Problem Statement
We have a grid with H rows and W columns. Each square is painted either white or black. For each integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, the color of the square at the i-th row from the top and j-th column from the left (we simply denote this square by Square (i, j)) is represented by A_{i, j}. Square (i, j) is white if A_{i, j} = 0, and black if A_{i, j} = 1.
You may perform the following operations any number of (possibly 0) times in any order:
- Choose an integer i such that 1 \leq i \leq H, pay R_i yen (the currency in Japan), and invert the color of each square in the i-th row from the top in the grid. (White squares are painted black, and black squares are painted white.)
- Choose an integer j such that 1 \leq j \leq W, pay C_j yen, and invert the color of each square in the j-th column from the left in the grid.
Print the minimum total cost to satisfy the following condition:
- There exists a path from Square (1, 1) to Square (H, W) that can be obtained by repeatedly moving down or to the right, such that all squares in the path (including Square (1, 1) and Square (H, W)) have the same color.
We can prove that it is always possible to satisfy the condition in a finite number of operations under the Constraints of this problem.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the answer.
Sample Input 1
3 4 4 3 5 2 6 7 4 0100 1011 1010
Sample Output 1
9
We denote a white square by 0 and a black square by 1.
On the initial grid, you can pay R_2 = 3 yen to invert the color of each square in the 2-nd row from the top to make the grid:
0100 0100 1010
Then, you can pay C_2 = 6 yen to invert the color of each square in the 2-nd row from the left to make the grid:
0000 0000 1110
Now, there exists a path from Square (1, 1) to Square (3, 4) such that all squares in the path have the same color (such as the path (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)). The total cost paid is 3+6 = 9 yen, which is the minimum possible.
Sample Input 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
Sample Output 2
125