O pobre bobo está preso num labirinto!

O labirinto está dividido em $n$ linhas e $m$ colunas. Cada célula do labirinto contém uma parede ao longo de uma diagonal. Portanto, há apenas dois tipos de células.

Graças ao seu poder mágico, bobo pode mudar o tipo da célula $(i, j)$ com custo $c_{i,j}$. Como um mago bondoso, bobo quer fazer com que o labirinto não possa mais prender ninguém. Isto é, não deve existir nenhuma região fechada cercada por paredes.

Encontre o custo total mínimo para que bobo alcance o objetivo.

Entrada

A primeira linha contém 2 inteiros $n, m$ ($1 \le n, m \le 1000$).

Cada uma das $n$ linhas seguintes contém $m$ caracteres, que indicam a direção da parede na célula.

Cada uma das últimas $n$ linhas contém $m$ inteiros $c_{i,1}, c_{i,2}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

Saída

Um único número que indica o custo mínimo.

Exemplos

Entrada 1

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

Saída 1

2

Entrada 2

2 2
\/
/\
1000 1000
1000 1000

Saída 2

0