Biedny bobo utknął w labiryncie!

Labirynt jest podzielony na $n$ wierszy i $m$ kolumn. Każda komórka labiryntu zawiera ścianę biegnącą wzdłuż przekątnej. Istnieją więc tylko dwa typy komórek.

Dzięki swojej magicznej mocy bobo może zmienić typ komórki $(i, j)$ za koszt $c_{i,j}$. Jako dobry czarodziej bobo chciałby sprawić, aby labirynt nie mógł już nikogo uwięzić. Innymi słowy, nie może pozostać żaden zamknięty obszar otoczony ścianami.

Znajdź minimalny łączny koszt osiągnięcia tego celu przez bobo.

Wejście

Pierwszy wiersz zawiera 2 liczby całkowite $n, m$ ($1 \le n, m \le 1000$).

Każdy z kolejnych $n$ wierszy zawiera $m$ znaków oznaczających kierunek ściany w komórce.

Każdy z ostatnich $n$ wierszy zawiera $m$ liczb całkowitych $c_{i,1}, c_{i,2}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

Wyjście

Jedna liczba oznaczająca minimalny koszt.

Przykład

Wejście 1

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

Wyjście 1

2

Wejście 2

2 2
\/
/\
1000 1000
1000 1000

Wyjście 2

0