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.

Input

The first line contains 2 integers $n, m$ ($1 \le n, m \le 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}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

Output

A single number denotes the minimum of cost.

Examples

Input 1

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

Output 1

2

Input 2

2 2
\/
/\
1000 1000
1000 1000

Output 2

0