Walls

Poor bobo is trapped in a maze!

The maze is divided into $n$ rows and $m$ columns. Each cell of the maze contains a wall across the diagonal. Thus, there are only two types of cells.

Thanks to bobo's magic power, he can change the type of cell $(i, j)$ with cost $c_{i, j}$. As a kind magician, bobo would like to make the maze unable to trap people anymore. That is to say, there will be no closed area surrounded by walls.

Find the minimum total cost for bobo to achieve the goal.

The first line contains $2$ integers $n, m$ ($1 \leq n, m \leq 1000$).

Each of the following $n$ lines contains $m$ characters, which denotes the direction of wall in the cell.

Each of the last $n$ lines contains $m$ integers $c_{i, 1}, c_{i, 2}, \dots, c_{i, m}$ ($1 \leq c_{i, j} \leq 1000$).

A single number denotes the minimum of cost.