벽

불쌍한 bobo가 미로에 갇혔다.

미로는 $n$개의 행과 $m$개의 열로 나뉘어 있다. 각 칸에는 대각선을 따라 벽이 하나씩 있으므로, 칸의 종류는 두 가지뿐이다.

bobo는 마법의 힘으로 칸 $(i, j)$의 종류를 비용 $c_{i,j}$를 내고 바꿀 수 있다. 착한 마법사인 bobo는 미로가 더 이상 사람을 가둘 수 없게 만들고 싶어 한다. 즉, 벽으로 둘러싸인 닫힌 영역이 없어야 한다.

bobo가 이 목표를 이루는 데 드는 최소 총비용을 구하라.

첫 줄에 정수 $n$, $m$이 주어진다 ($1 \leq n, m \leq 1000$).

이어지는 $n$개의 줄에는 각각 $m$개의 문자가 주어지며, 각 칸에 있는 벽의 방향을 나타낸다.

마지막 $n$개의 줄에는 각각 $m$개의 정수 $c_{i,1}, c_{i,2}, \dots, c_{i,m}$이 주어진다 ($1 \leq c_{i,j} \leq 1000$).

최소 비용을 나타내는 정수 하나를 출력한다.