Бедный 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