from collections import deque import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 7) DX = (-1, 0, 1, 0, -1, -1, 1, 1) DY = (0, 1, 0, -1, -1, 1, -1, 1) DX = DX[:4] DY = DY[:4] class MF_graph(object): def __init__(self, n): self.n = n self.g = [[] for _ in range(n)] # to, rev, cap self.pos = [] def add_edge(self, frm, to, cap): """ frmからtoへ容量cap, 流量0の辺を追加, 何番目の辺かを返す""" m = len(self.pos) self.pos.append((frm, len(self.g[frm]))) self.g[frm].append([to, len(self.g[to]), cap]) self.g[to].append([frm, len(self.g[frm]) - 1, 0]) return m def get_edge(self, i): e_to, e_rev, e_cap = self.g[self.pos[i][0]][self.pos[i][1]] re_to, _, re_cap = self.g[e_to][e_rev] # from, to, cap, flow return (re_to, e_to, e_cap + re_cap, re_cap) def edges(self): m = len(self.pos) for i in range(m): yield self.get_edge(i) def change_edge(self, i, new_cap, new_flow): """ i番目に追加された辺の容量,流量をnew_cap, new_flowに変更する """ f, s = self.pos[i] rf, rs, _ = self.g[f][s] self.g[f][s][2] = new_cap - new_flow self.g[rf][rs][2] = new_flow return def __dfs(self, s, v, up): if v == s: return up res = 0 level_v = self.level[v] for i in range(self.iter[v], len(self.g[v])): u_to, u_rev, _ = self.g[v][i] if level_v <= self.level[u_to] or self.g[u_to][u_rev][2] == 0: continue d = self.__dfs(s, u_to, min(up - res, self.g[u_to][u_rev][2])) if d <= 0: continue self.g[v][i][2] += d self.g[u_to][u_rev][2] -= d res += d if res == up: break return res def flow(self, s, t, flow_limit=10**18): """ sからtへflow_limitだけ流す。流せた量を返す """ self.iter = [0] * self.n flow = 0 while flow < flow_limit: self.level = [-1] * self.n self.level[s] = 0 que = deque([s]) while que: v = que.popleft() for u_to, _, u_cap in self.g[v]: if u_cap == 0 or self.level[u_to] >= 0: continue self.level[u_to] = self.level[v] + 1 if u_to == t: break que.append(u_to) if self.level[t] == -1: break self.iter = [0] * self.n while flow < flow_limit: f = self.__dfs(s, t, flow_limit - flow) if not f: break flow += f return flow def min_cut(self, s): """ 最小カットを返す。sから到達可能だとTrue """ visited = [False] * self.n que = deque([s]) while que: v = que.popleft() visited[v] = True for u_to, _, u_cap in self.g[v]: if u_cap and (not visited[u_to]): visited[u_to] = True que.append(u_to) return visited N, M = map(int, input().split()) S = [input().rstrip() for _ in range(N)] source = N * M sink = source + 1 G = MF_graph(N * M + 2) black = 0 white = 0 for x in range(N): for y in range(M): if S[x][y] == ".": continue if (x + y) % 2 == 0: white += 1 G.add_edge(source, x * M + y, 1) for dx, dy in zip(DX, DY): nx = x + dx ny = y + dy if 0 <= nx < N and 0 <= ny < M and S[nx][ny] != ".": G.add_edge(x * M + y, nx * M + ny, 1) else: black += 1 G.add_edge(x * M + y, sink, 1) ans = 0 flow = G.flow(source, sink) ans += 100 * flow black -= flow white -= flow d = min(black, white) ans += 10 * d black -= d white -= d ans += black + white print(ans)