#include #define FOR(v, a, b) for(int v = (a); v < (b); ++v) #define FORE(v, a, b) for(int v = (a); v <= (b); ++v) #define REP(v, n) FOR(v, 0, n) #define REPE(v, n) FORE(v, 0, n) #define REV(v, a, b) for(int v = (a); v >= (b); --v) #define ALL(x) (x).begin(), (x).end() #define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it) #define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it) #define EXIST(c,x) ((c).find(x) != (c).end()) #define LLI long long int #define fst first #define snd second #ifdef DEBUG #include #else #define dump(x) ((void)0) #endif using namespace std; #define gcd __gcd template constexpr T lcm(T m, T n){return m/gcd(m,n)*n;} template void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost< istream& operator>>(istream &is, vector &v){for(auto &a : v) is >> a; return is;} template istream& operator>>(istream &is, pair &p){is >> p.first >> p.second; return is;} template T& chmin(T &a, const U &b){return a = (a<=b?a:b);} template T& chmax(T &a, const U &b){return a = (a>=b?a:b);} template void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);} template class Dinic{ private: vector>> graph; int size, s, t; vector> cap; vector level; bool buildLevel(){ fill(ALL(level), 0); level[s] = 1; deque deq = {s}; while(!deq.empty()){ int cur = deq.front(); deq.pop_front(); REP(i,size) if(level[i]==0 && cap[cur][i]>0){ level[i] = level[cur] + 1; deq.push_back(i); } } return level[t] != 0; } void dfs(vector &path, T &flow){ if(path.empty()) return; int cur = path.back(); if(cur == t){ T f = INF; FOR(i,1,path.size()) f = min(f, cap[path[i-1]][path[i]]); FOR(i,1,path.size()){ cap[path[i-1]][path[i]] -= f; cap[path[i]][path[i-1]] += f; } flow += f; }else{ REP(i,size){ if(cap[cur][i]>0 && level[i]>level[cur]){ path.push_back(i); dfs(path, flow); path.pop_back(); } } } } T augment(){ T f = 0; vector path = {s}; dfs(path, f); return f; } T loop(){ T f = 0; while(buildLevel()) f += augment(); return f; } public: Dinic(vector>> &_graph): graph(_graph), size(graph.size()) {} Dinic(int size): graph(size), size(size){} void add_edge(int from, int to, const T &cap){ graph[from].push_back({to, cap}); } T max_flow(int _s, int _t){ cap = vector>(size, vector(size, 0)); level = vector(size, 0); REP(i,size) for(auto &p : graph[i]){ int j = p.first; T d = p.second; cap[i][j] += d; } s = _s; t = _t; return loop(); } }; class BipartiteMatching{ public: int x, y; Dinic mflow; int s, t; BipartiteMatching(int x, int y): x(x), y(y), mflow(x+y+2), s(x+y), t(s+1){ REP(i,x) mflow.add_edge(s,i,1); REP(i,y) mflow.add_edge(x+i,t,1); } void add_edge(int i, int j){ mflow.add_edge(i,x+j,1); } int matching(){ return mflow.max_flow(s,t); } }; const int dir4[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,M; while(cin >> N >> M){ vector S(N); cin >> S; int c = 0; REP(i,N) REP(j,M) if(S[i][j] != '.') ++c; BipartiteMatching bm(N*M,N*M); vector> w(N, vector(M,-1)), b(N, vector(M,-1)); int cw=0, cb=0; REP(i,N) REP(j,M){ if(S[i][j] == 'w') w[i][j] = cw++; if(S[i][j] == 'b') b[i][j] = cb++; } REP(i,N){ REP(j,M){ for(auto &d : dir4){ int y=i+d[0], x=j+d[1]; if(y<0 or y>=N or x<0 or x>=M) continue; if(S[i][j] == 'w' and S[y][x] == 'b') bm.add_edge(w[i][j], b[y][x]); } } } int mat = bm.matching(); int ans = mat*100 + (c-mat*2)/2*10 + c%2; cout << ans << endl; } return 0; }