Бідолашний bobo потрапив у пастку в лабіринті!

Лабіринт поділено на $n$ рядків і $m$ стовпців. У кожній клітинці лабіринту є стіна вздовж діагоналі. Отже, існує лише два типи клітинок.

Завдяки своїй магічній силі bobo може змінити тип клітинки $(i, j)$ за вартість $c_{i,j}$. Як добрий чарівник, bobo хоче зробити так, щоб лабіринт більше нікого не міг ув'язнити. Тобто не має залишитися жодної замкненої ділянки, оточеної стінами.

Знайдіть мінімальну загальну вартість досягнення мети bobo.

Вхідні дані

Перший рядок містить 2 цілих числа $n, m$ ($1 \le n, m \le 1000$).

Кожен із наступних $n$ рядків містить $m$ символів, які позначають напрямок стіни в клітинці.

Кожен з останніх $n$ рядків містить $m$ цілих чисел $c_{i,1}, c_{i,2}, \ldots, c_{i,m}$ ($1 \le c_{i,j} \le 1000$).

Вихідні дані

Одне число, що позначає мінімальну вартість.

Приклади

Вхідні дані 1

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

Вихідні дані 1

2

Вхідні дані 2

2 2
\/
/\
1000 1000
1000 1000

Вихідні дані 2

0