#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; typedef pair Q; typedef complex C; #define cx real() #define cy imag() const ll INF = 1LL << 60; const double DINF = 1e30; const ll mod = 1000000007; const ll dx[4] = {1, 0, -1, 0}; const ll dy[4] = {0, -1, 0, 1}; const C I = C(0, 1); const double EPS = 1e-10; const ll NCK_MAX = 510000; ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } ll extgcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1, y = 0; return a; } ll q = a/b, g = extgcd(b, a - q*b, x, y); ll z = x - q * y; x = y; y = z; return g; } ll invmod (ll a, ll m) { // a^-1 mod m ll x, y; extgcd(a, m, x, y); x %= m; if (x < 0) x += m; return x; } ll *fac, *finv, *inv; void nCk_init(ll mod) { fac = new ll[NCK_MAX]; finv = new ll[NCK_MAX]; inv = new ll[NCK_MAX]; fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (ll i = 2; i < NCK_MAX; i++) { fac[i] = fac[i-1] * i % mod; inv[i] = mod - inv[mod%i] * (mod / i) % mod; finv[i] = finv[i-1] * inv[i] % mod; } } ll nCk(ll n, ll k, ll mod) { if (fac == NULL) nCk_init(mod); if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n-k] % mod) % mod; } template class Zip { vector d; bool flag; void init() { sort(d.begin(), d.end()); d.erase(unique(d.begin(), d.end()), d.end()); flag = false; } public: Zip() { flag = false; } void add(T x) { d.push_back(x); flag = true; } ll getNum(T x) { if (flag) init(); return lower_bound(d.begin(), d.end(), x) - d.begin(); } ll size() { if (flag) init(); return (ll)d.size(); } }; class UnionFind { vector par, rank; // par > 0: number, par < 0: -par public: void init(ll n) { par.resize(n); rank.resize(n); fill(par.begin(), par.end(), 1); fill(rank.begin(), rank.end(), 0); } ll getSize(ll x) { return par[find(x)]; } ll find(ll x) { if (par[x] > 0) return x; return -(par[x] = -find(-par[x])); } void merge(ll x, ll y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) { par[y] += par[x]; par[x] = -y; } else { par[x] += par[y]; par[y] = -x; if (rank[x] == rank[y]) rank[x]++; } } bool isSame(ll x, ll y) { return find(x) == find(y); } }; template class SegmentTree { ll n; vector node; function fun, fun2; bool customChange; T outValue, initValue; public: void init(ll num, function resultFunction, T init, T out, function changeFunction = NULL) { // changeFunction: (input, beforevalue) => newvalue fun = resultFunction; fun2 = changeFunction; customChange = changeFunction != NULL; n = 1; while (n < num) n *= 2; node.resize(2 * n - 1); fill(node.begin(), node.end(), init); outValue = out; initValue = init; } void valueChange(ll num, T value) { num += n-1; if (customChange) node[num] = fun2(value, node[num]); else node[num] = value; while (num > 0) num = (num - 1) / 2, node[num] = fun(node[num * 2 + 1], node[num * 2 + 2]); } T rangeQuery(ll a, ll b, ll l = 0, ll r = -1, ll k = 0) { // [a, b) if (r == -1) r = n; if (a <= l && r <= b) return node[k]; if (b <= l || r <= a) return outValue; ll mid = (l + r) / 2; return fun(rangeQuery(a, b, l, mid, 2*k+1), rangeQuery(a, b, mid, r, 2*k+2)); } }; template class Graph { struct edge { ll to; T cost; }; struct edge_data { ll from, to; T cost; }; ll v; vector> e, re; vector ed; vector used; vector vs, cmp; bool isDirected, isMinasEdge; public: Graph(ll _v, bool _isDirected = true) { //_v++; v = _v, isDirected = _isDirected; isMinasEdge = false; e.resize(v), re.resize(v); } void add_edge(ll s, ll t, T cost = 1) { e[s].push_back((edge){t, cost}); if (!isDirected) e[t].push_back((edge){s, cost}); else re[t].push_back((edge){s, cost}); ed.push_back((edge_data){s, t, cost}); if (cost < 0) isMinasEdge = true; } vector dijkstra(ll s) { vector d(v, INF); d[s] = 0; auto edge_cmp = [](const edge& a, const edge& b) { return a.cost > b.cost; }; priority_queue, decltype(edge_cmp)> pq(edge_cmp); pq.push((edge){s, 0}); while (!pq.empty()) { edge temp = pq.top(); pq.pop(); if (d[temp.to] < temp.cost) continue; for (const edge& next : e[temp.to]) { T cost = temp.cost + next.cost; if (d[next.to] > cost) { d[next.to] = cost; pq.push((edge){next.to, cost}); } } } return d; } vector bellmanford(ll s) { vector d(v, INF); d[s] = 0; for (ll i = 0; i < v; i++) { for (const edge_data& temp : ed) { if (d[temp.from] != INF && d[temp.to] > d[temp.from] + temp.cost) d[temp.to] = d[temp.from] + temp.cost; if (!isDirected && d[temp.to] != INF && d[temp.from] > d[temp.to] + temp.cost) d[temp.from] = d[temp.to] + temp.cost; } } for (ll i = 0; i < v; i++) { for (const edge_data& temp : ed) { if (d[temp.from] != INF && d[temp.to] > d[temp.from] + temp.cost) d[temp.to] = -INF; if (!isDirected && d[temp.to] != INF && d[temp.from] > d[temp.to] + temp.cost) d[temp.from] = -INF; } } return d; } vector shortest_path(ll s) { if (isMinasEdge) return bellmanford(s); else return dijkstra(s); } T kruskal() { // if (isDirected) UnionFind uf; uf.init(v); auto edge_data_cmp = [](const edge_data& a, const edge_data& b) { return a.cost < b.cost; }; sort(ed.begin(), ed.end(), edge_data_cmp); T ans = 0; for (const edge_data& temp : ed) { if (uf.isSame(temp.from, temp.to)) continue; uf.merge(temp.from, temp.to); ans += temp.cost; } return ans; } void scc_dfs(ll s) { used[s] = true; for (const edge& i : e[s]) if (!used[i.to]) scc_dfs(i.to); vs.push_back(s); } void scc_rdfs(ll s, ll k) { used[s] = true; cmp[s] = k; for (const edge& i : re[s]) if (!used[i.to]) scc_rdfs(i.to, k); } vector scc() { used.resize(v); fill(used.begin(), used.end(), false); cmp.resize(v); vs.clear(); for (ll i = 0; i < v; i++) if (!used[i]) scc_dfs(i); used.resize(v); fill(used.begin(), used.end(), false); ll k = 0; for (ll i = vs.size() - 1; i >= 0; i--) if (!used[vs[i]]) scc_rdfs(vs[i], k++); return cmp; } }; template class Flow { struct edge { ll to; T cap; ll rev; }; vector > G; vector level, iter; bool isDirected; public: Flow(ll n, bool _isDirected = true) : G(n), level(n), iter(n), isDirected(_isDirected) {} void add_edge(ll from, ll to, T cap) { G[from].emplace_back((edge){to, cap, (ll)G[to].size()}); G[to].emplace_back((edge){from, isDirected ? 0LL : cap, (ll)G[from].size()-1}); //return G[to].back().rev; } void bfs(ll s) { fill(level.begin(), level.end(), -1); queue que; level[s] = 0; que.emplace(s); while (!que.empty()) { ll v=que.front(); que.pop(); for (ll i=0; i < (ll)G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v]+1; que.emplace(e.to); } } } } T dfs(ll v, ll t, T f) { if (v == t) return f; for (ll &i = iter[v]; i < (ll)G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { T d = dfs(e.to, t, min(f, e.cap)); if (d == 0) continue; e.cap -= d; G[e.to][e.rev].cap += d; return d; } } return 0; } T maxflow(ll s, ll t, T lim = INF) { T fl = 0; while (1) { bfs(s); if (level[t] < 0 || lim == 0) break; fill(iter.begin(), iter.end(), 0); while(1) { T f = dfs(s, t, lim); if(f == 0) break; fl += f; lim -= f; } } return fl; } }; class BipartiteMatching { vector pre, root; vector> to; vector p, q; ll n, m; public: BipartiteMatching(ll n, ll m) : pre(n, -1), root(n, -1), to(n), p(n, -1), q(m, -1), n(n), m(m){} void add_edge(ll a, ll b) { to[a].push_back(b);} ll solve() { ll res = 0; bool upd = true; while (upd) { upd = false; queue s; for (ll i = 0; i < n; ++i) { if (!~p[i]) { root[i] = i; s.push(i); } } while (!s.empty()) { ll v = s.front(); s.pop(); if (~p[root[v]]) continue; for (ll i = 0; i < (ll)to[v].size(); ++i) { ll u = to[v][i]; if (!~q[u]) { while (~u) { q[u] = v; swap(p[v],u); v = pre[v]; } upd = true; ++res; break; } u = q[u]; if (~pre[u]) continue; pre[u] = v; root[u] = root[v]; s.push(u); } } if (upd) fill(pre.begin(),pre.end(),-1), fill(root.begin(),root.end(),-1); } return res; } }; template< typename flow_t, typename cost_t > struct PrimalDual { const cost_t INF; struct edge { int to; flow_t cap; cost_t cost; int rev; bool isrev; }; vector< vector< edge > > graph; vector< cost_t > potential, min_cost; vector< int > prevv, preve; PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {} void add_edge(int from, int to, flow_t cap, cost_t cost) { graph[from].emplace_back((edge) {to, cap, cost, (int) graph[to].size(), false}); graph[to].emplace_back((edge) {from, 0, -cost, (int) graph[from].size() - 1, true}); } cost_t min_cost_flow(int s, int t, flow_t f) { int V = (int) graph.size(); cost_t ret = 0; using Pi = pair< cost_t, int >; priority_queue< Pi, vector< Pi >, greater< Pi > > que; potential.assign(V, 0); preve.assign(V, -1); prevv.assign(V, -1); while(f > 0) { min_cost.assign(V, INF); que.emplace(0, s); min_cost[s] = 0; while(!que.empty()) { Pi p = que.top(); que.pop(); if(min_cost[p.second] < p.first) continue; for(int i = 0; i < graph[p.second].size(); i++) { edge &e = graph[p.second][i]; cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to]; if(e.cap > 0 && min_cost[e.to] > nextCost) { min_cost[e.to] = nextCost; prevv[e.to] = p.second, preve[e.to] = i; que.emplace(min_cost[e.to], e.to); } } } if(min_cost[t] == INF) return -1; for(int v = 0; v < V; v++) potential[v] += min_cost[v]; flow_t addflow = f; for(int v = t; v != s; v = prevv[v]) { addflow = min(addflow, graph[prevv[v]][preve[v]].cap); } f -= addflow; ret += addflow * potential[t]; for(int v = t; v != s; v = prevv[v]) { edge &e = graph[prevv[v]][preve[v]]; e.cap -= addflow; graph[v][e.rev].cap += addflow; } } return ret; } }; ll n, m, b, w; char s[50][51]; int main() { scanf("%lld%lld", &n, &m); for (ll i = 0; i < n; i++) scanf("%s", s[i]); for (ll i = 0; i < n; i++) for (ll j = 0; j < m; j++) if (s[i][j] == 'w') w++; else if (s[i][j] == 'b') b++; BipartiteMatching bm(m*n, m*n); for (ll i = 0; i < n; i++) for (ll j = 0; j < m; j++) if (s[i][j] == 'w') { for (ll k = 0; k < 4; k++) { ll x = i + dx[k], y = j + dy[k]; if (x < 0 || y < 0 || x == n || y == m) continue; if (s[x][y] == 'b') bm.add_edge(i*m+j, x*m+y); } } ll num = bm.solve(); ll mn = min(b, w) - num; printf("%lld\n", 100LL*num + 10 * mn + (max(b, w) - min(b, w))); }