from collections import deque class HopcroftKarp: def __init__(self, graph, U, V): self.graph = graph # adjacency list for left nodes (U) self.U = U self.V = V self.pair_u = [-1] * U # pair for left nodes self.pair_v = [-1] * V # pair for right nodes self.dist = [0] * U # distance for BFS def bfs(self): queue = deque() for u in range(self.U): if self.pair_u[u] == -1: self.dist[u] = 0 queue.append(u) else: self.dist[u] = float('inf') self.dist_null = float('inf') while queue: u = queue.popleft() if self.dist[u] < self.dist_null: for v in self.graph[u]: if self.pair_v[v] == -1: self.dist_null = self.dist[u] + 1 elif self.dist[self.pair_v[v]] == float('inf'): self.dist[self.pair_v[v]] = self.dist[u] + 1 queue.append(self.pair_v[v]) return self.dist_null != float('inf') def dfs(self, u): if u != -1: for v in self.graph[u]: if self.pair_v[v] == -1 or (self.dist[self.pair_v[v]] == self.dist[u] + 1 and self.dfs(self.pair_v[v])): self.pair_u[u] = v self.pair_v[v] = u return True self.dist[u] = float('inf') return False return True def max_matching(self): result = 0 while self.bfs(): for u in range(self.U): if self.pair_u[u] == -1: if self.dfs(u): result += 1 return result def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx += 1 M = int(input[idx]) idx += 1 grid = [] for _ in range(N): grid.append(input[idx].strip()) idx += 1 w_positions = [] b_positions = [] for i in range(N): for j in range(M): c = grid[i][j] if c == 'w': w_positions.append((i, j)) elif c == 'b': b_positions.append((i, j)) U = len(w_positions) V = len(b_positions) if U == 0 or V == 0: print(0) return graph = [[] for _ in range(U)] b_map = {(i, j): idx for idx, (i, j) in enumerate(b_positions)} dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] for u in range(U): i, j = w_positions[u] for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < N and 0 <= nj < M: if grid[ni][nj] == 'b' and (ni, nj) in b_map: v = b_map[(ni, nj)] graph[u].append(v) hk = HopcroftKarp(graph, U, V) k = hk.max_matching() total_w = U total_b = V remaining_w = total_w - k remaining_b = total_b - k m = min(remaining_w, remaining_b) score = 100 * k + 10 * m + (remaining_w + remaining_b - 2 * m) print(score) if __name__ == "__main__": main()