시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB18121275.000%

문제

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.

예제 입력 1

3 3
/\/
\/\
/\/
1 3 3
3 1 3
3 3 3

예제 출력 1

2

예제 입력 2

2 2
\/
/\
1000 1000
1000 1000

예제 출력 2

0