#include using namespace std; using ll = long long; using PII = pair; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template void chmin(T &a, const T &b) { a = min(a, b); } template void chmax(T &a, const T &b) { a = max(a, b); } struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio; #ifdef DEBUG_ #include "../program_contest_library/memo/dump.hpp" #else #define dump(...) #endif const ll INF = 1LL<<60; struct min_cost_max_flow { struct edge { int to; ll cap, cost; int rev; bool isrev; }; int n, s, t; ll neg; vector> g; vector d, h, dist, prevv, preve; ll flow(vector d0) { ll res = 0; priority_queue, greater> que; h.assign(n, 0); preve.assign(n, -1); prevv.assign(n, -1); ll f = 0; REP(i, d.size()) { if(i < (ll)d0.size()) d[i] += d0[i]; if(d[i] > 0) add_edge(s, i, d[i], 0), f += d[i]; else add_edge(i, t, -d[i], 0); } while(f > 0) { dist.assign(n, INF); dist[s] = 0; que.push({0, s}); while(que.size()) { PII p = que.top(); que.pop(); int v = p.second; if(dist[v] < p.first) continue; REP(i, g[v].size()) { edge &e = g[v][i]; if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; que.push({dist[e.to], e.to}); } } } if(dist[t] == INF) return -1; REP(v, n) h[v] += dist[v]; ll d = f; for(int v = t; v != s; v = prevv[v]) { chmin(d, g[prevv[v]][preve[v]].cap); } f -= d; res += d * h[t]; for(int v = t; v != s; v = prevv[v]) { edge &e = g[prevv[v]][preve[v]]; e.cap -= d; g[v][e.rev].cap += d; } } return neg + res; } min_cost_max_flow(int n0) : n(n0+2), s(n0), t(n0+1), neg(0), g(n0+2), d(n0+2) {} void add_edge(int from, int to, ll cap, ll cost) { if(cost >= 0) { g[from].push_back({to, cap, cost, (int)g[to].size(), true}); g[to].push_back({from, 0, -cost, (int)g[from].size()-1, false}); } else { d[from] -= cap; d[to] += cap; neg += cap * cost; add_edge(to, from, cap, -cost); } } // SからTに流量fを流す // 流せないなら-1 ll flow(int S, int T, ll f) { vector d0(n); d0[S] = f, d0[T] = -f; return flow(d0); } }; int main(void) { ll h, w; cin >> h >> w; vector a(h); REP(i, h) cin >> a[i]; min_cost_max_flow graph(h*w+2); ll s = h*w, t = s+1, f = 0; REP(i, h) REP(j, w) { if(a[i][j]=='w') { graph.add_edge(s, i*w+j, 1, 0); graph.add_edge(i*w+j, t, 1, -1); f++; } else { graph.add_edge(s, i*w+j, 1, -1); graph.add_edge(i*w+j, t, 1, 0); } if(a[i][j]!='w') continue; REP(y, h) REP(x, w) { if(a[y][x]!='b') continue; if(abs(y-i)+abs(x-j) == 1) { graph.add_edge(i*w+j, y*w+x, 1, -100); } else { graph.add_edge(i*w+j, y*w+x, 1, -10); } } } cout << -graph.flow(s, t, f) << endl; return 0; }