¡El pobre bobo está atrapado en un laberinto!

El laberinto está dividido en $n$ filas y $m$ columnas. Cada celda del laberinto contiene un muro a lo largo de una diagonal. Por tanto, solo hay dos tipos de celdas.

Gracias a su poder mágico, bobo puede cambiar el tipo de la celda $(i, j)$ con un coste de $c_{i,j}$. Como mago bondadoso, bobo quiere hacer que el laberinto ya no pueda atrapar a nadie. Es decir, no debe quedar ninguna región cerrada rodeada por muros.

Encuentra el coste total mínimo para que bobo alcance su objetivo.

Entrada

La primera línea contiene 2 enteros $n, m$ ($1 \le n, m \le 1000$).

Cada una de las siguientes $n$ líneas contiene $m$ caracteres, que indican la dirección del muro de la celda.

Cada una de las últimas $n$ líneas contiene $m$ enteros $c_{i,1}, c_{i,2}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

Salida

Un único número que indica el coste mínimo.

Ejemplos

Entrada 1

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

Salida 1

2

Entrada 2

2 2
\/
/\
1000 1000
1000 1000

Salida 2

0