Le pauvre bobo est piégé dans un labyrinthe !

Le labyrinthe est divisé en $n$ lignes et $m$ colonnes. Chaque case du labyrinthe contient un mur le long d'une diagonale. Il n'existe donc que deux types de cases.

Grâce à ses pouvoirs magiques, bobo peut changer le type de la case $(i, j)$ pour un coût de $c_{i,j}$. En bon magicien, bobo souhaite que le labyrinthe ne puisse plus piéger personne. Autrement dit, il ne doit plus exister de région fermée entourée de murs.

Trouvez le coût total minimal permettant à bobo d'atteindre son objectif.

Entrée

La première ligne contient 2 entiers $n, m$ ($1 \le n, m \le 1000$).

Chacune des $n$ lignes suivantes contient $m$ caractères indiquant la direction du mur dans la case.

Chacune des $n$ dernières lignes contient $m$ entiers $c_{i,1}, c_{i,2}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

Sortie

Un seul nombre indiquant le coût minimal.

Exemples

Entrée 1

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

Sortie 1

2

Entrée 2

2 2
\/
/\
1000 1000
1000 1000

Sortie 2

0