Der arme bobo ist in einem Labyrinth gefangen!

Das Labyrinth ist in $n$ Zeilen und $m$ Spalten unterteilt. Jede Zelle des Labyrinths enthält eine Wand entlang einer Diagonalen. Es gibt also nur zwei Arten von Zellen.

Dank seiner magischen Kräfte kann bobo den Typ der Zelle $(i, j)$ zu Kosten von $c_{i,j}$ ändern. Als gutherziger Zauberer möchte bobo erreichen, dass das Labyrinth niemanden mehr gefangen halten kann. Das heißt, es darf keinen geschlossenen, von Wänden umgebenen Bereich mehr geben.

Finde die minimalen Gesamtkosten, mit denen bobo dieses Ziel erreichen kann.

Eingabe

Die erste Zeile enthält 2 ganze Zahlen $n, m$ ($1 \le n, m \le 1000$).

Jede der folgenden $n$ Zeilen enthält $m$ Zeichen, welche die Richtung der Wand in der Zelle angeben.

Jede der letzten $n$ Zeilen enthält $m$ ganze Zahlen $c_{i,1}, c_{i,2}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

Ausgabe

Eine einzelne Zahl gibt die minimalen Kosten an.

Beispiele

Eingabe 1

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

Ausgabe 1

2

Eingabe 2

2 2
\/
/\
1000 1000
1000 1000

Ausgabe 2

0