#include #include #include #include #include #include #include #include #include #include #include static const int MOD = 1000000007; using ll = long long; using u32 = uint32_t; using namespace std; template constexpr T INF = ::numeric_limits::max() / 32 * 15 + 208; class Bipartite_Matching { vector> G; vector used, alive; int t; public: vector match; explicit Bipartite_Matching(int n): t(0), G(n), used(n, 0), alive(n, -1), match(n, -1) {}; void add_edge(int a, int b){ G[a].emplace_back(b); G[b].emplace_back(a); } bool dfs(int x){ used[x] = t; for (auto &&i : G[x]) { int w = match[i]; if(alive[i] == 0) continue; if(w == -1 || (used[w] != t && dfs(w))){ match[x] = i; match[i] = x; return true; } } return false; } int matching() { int ans = 0; for (int i = 0; i < G.size(); ++i) { if(alive[i] == 0) continue; if(match[i] == -1) { ++t; ans += dfs(i); } } return ans; } }; int main() { int h, w; cin >> h >> w; vector> v(h+2, vector (w+2, 0)); for (int i = 0; i < h; ++i) { string s; cin >> s; for (int j = 0; j < w; ++j) { v[i+1][j+1] = s[j] != '.'; } } Bipartite_Matching G(h*w); array dx{-1, 1, 0, 0}, dy{0, 0, -1, 1}; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if(!v[i+1][j+1]) continue; for (int k = 0; k < 4; ++k) { if(v[i+1+dy[k]][j+1+dx[k]]){ G.add_edge(i*w+j, (i+dy[k])*w+j+dx[k]); } } } } ll ans = G.matching()*100, a = 0, b = 0; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if(!v[i+1][j+1]) continue; if(!(~G.match[i*w+j])){ ((i+j)%2 ? a : b)++; } } } cout << ans + min(a, b)*9 + max(a, b); return 0; }