#include #include #include #include #include #include using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (n); i++) template using vi = vector; template using vii = vector>; template using viii = vector>; struct Dinic { struct edge { int to, rev; ll cap; edge(int t = 0, int r = 0, ll c = 0) : to(t), rev(r), cap(c) {} }; int n; vii to; vi iter; vi dist; Dinic(int n_ = 0) : n(n_), to(n_), iter(n_), dist(n_) {} void addedge(int u, int v, ll cap) { int su = (int)to[u].size(); int sv = (int)to[v].size(); to[u].push_back({ v, sv, cap }); to[v].push_back({ u, su, 0 }); } void bfs(int s) { dist.assign(n, -1); dist[s] = 0; queue q; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); for (edge& nv : to[v]) { if (dist[nv.to] >= 0 || nv.cap == 0) continue; dist[nv.to] = dist[v] + 1; q.push(nv.to); } } } ll dfs(int v, int t, ll f = 1e18) { if (v == t) return f; int sv = (int)to[v].size(); for (int& i = iter[v]; i < sv; i++) { edge& nv = to[v][i]; if (dist[nv.to] <= dist[v] || nv.cap == 0) continue; ll nf = dfs(nv.to, t, min(f, nv.cap)); if (nf > 0) { nv.cap -= nf; to[nv.to][nv.rev].cap += nf; return nf; } } return 0; } ll maxflow(int s, int t) { ll res = 0, flow = 0; while (true) { bfs(s); if (dist[t] < 0) break; iter.assign(n, 0); while (flow = dfs(s, t)) res += flow; } return res; } }; int main() { int n, m; cin >> n >> m; vi s(n); rep(i, n) cin >> s[i]; int dx[] = { 1, 0, -1, 0 }; int dy[] = { 0, 1, 0, -1 }; auto f = [&](int i, int j) { return m * i + j; }; Dinic dn(n * m + 2); int S = n * m, T = S + 1; int cw = 0, cb = 0; rep(i, n) rep(j, m) { if (s[i][j] == '.') continue; if ((i + j) & 1) { dn.addedge(f(i, j), T, 1); cb++; } else { dn.addedge(S, f(i, j), 1); cw++; rep(k, 4) { int ni = i + dx[k]; int nj = j + dy[k]; if (ni < 0 || ni >= n || nj < 0 || nj >= m || s[ni][nj] == '.') continue; dn.addedge(f(i, j), f(ni, nj), 1); } } } ll mf = dn.maxflow(S, T); cw -= mf, cb -= mf; ll res = mf * 100 + min(cw, cb) * 10 + cw + cb - 2 * min(cw, cb); cout << res << endl; return 0; }