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.

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}$
```

Print the answer.

-   $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.

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)→(2,1)→(2,2)→(2,3)→(2,4)→(3,4)). The total cost paid is 3+6=9 yen, which is the minimum possible.