bobo yang malang terjebak di dalam labirin!

Labirin dibagi menjadi $n$ baris dan $m$ kolom. Setiap sel labirin berisi dinding sepanjang diagonal. Jadi, hanya ada dua jenis sel.

Berkat kekuatan sihirnya, bobo dapat mengubah jenis sel $(i, j)$ dengan biaya $c_{i,j}$. Sebagai penyihir yang baik hati, bobo ingin membuat labirin tidak bisa lagi menjebak siapa pun. Artinya, tidak boleh ada daerah tertutup yang dikelilingi dinding.

Carilah total biaya minimum agar bobo mencapai tujuannya.

Masukan

Baris pertama berisi 2 bilangan bulat $n, m$ ($1 \le n, m \le 1000$).

Masing-masing dari $n$ baris berikutnya berisi $m$ karakter yang menyatakan arah dinding di dalam sel.

Masing-masing dari $n$ baris terakhir berisi $m$ bilangan bulat $c_{i,1}, c_{i,2}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

Keluaran

Sebuah angka yang menyatakan biaya minimum.

Contoh

Masukan 1

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

Keluaran 1

2

Masukan 2

2 2
\/
/\
1000 1000
1000 1000

Keluaran 2

0