#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define isz(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
const int INF = 1e9;
// Hopcroft–Karp trên đồ thị L (1..nL) – R (1..nR)
struct HopcroftKarp {
int nL, nR;
vector<vector<int>> adj;
vector<int> dist, pairU, pairV;
HopcroftKarp(int _nL, int _nR)
: nL(_nL), nR(_nR),
adj(_nL+1), dist(_nL+1),
pairU(_nL+1), pairV(_nR+1) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
bool bfs() {
queue<int> q;
FOR(u,1,nL) {
if (pairU[u] == 0) {
dist[u] = 0;
q.push(u);
} else {
dist[u] = INF;
}
}
dist[0] = INF;
while (!q.empty()) {
int u = q.front(); q.pop();
if (dist[u] < dist[0]) {
for (int v: adj[u]) {
if (dist[pairV[v]] == INF) {
dist[pairV[v]] = dist[u] + 1;
q.push(pairV[v]);
}
}
}
}
return dist[0] != INF;
}
bool dfs(int u) {
if (u == 0) return true;
for (int v: adj[u]) {
if (dist[pairV[v]] == dist[u] + 1 && dfs(pairV[v])) {
pairU[u] = v;
pairV[v] = u;
return true;
}
}
dist[u] = INF;
return false;
}
int maxMatching() {
int result = 0;
while (bfs()) {
FOR(u,1,nL) {
if (pairU[u] == 0 && dfs(u))
++result;
}
}
return result;
}
};
int n, m;
vector<string> grid;
void solve() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
grid.resize(n);
FOR(i,0,n-1) {
cin >> grid[i];
}
// Đánh dấu các đoạn chạy # theo hàng (horizontal runs)
vector<vector<int>> h_id(n, vector<int>(m, 0));
int cntH = 0;
FOR(i,0,n-1) {
FOR(j,0,m-1) {
if (grid[i][j] == '#') {
if (j == 0 || grid[i][j-1] == '.') {
++cntH;
}
h_id[i][j] = cntH;
}
}
}
// Đánh dấu các đoạn chạy # theo cột (vertical runs)
vector<vector<int>> v_id(n, vector<int>(m, 0));
int cntV = 0;
FOR(j,0,m-1) {
FOR(i,0,n-1) {
if (grid[i][j] == '#') {
if (i == 0 || grid[i-1][j] == '.') {
++cntV;
}
v_id[i][j] = cntV;
}
}
}
// Xây dựng đồ thị song phân: H (1..cntH) – V (1..cntV)
HopcroftKarp hk(cntH, cntV);
FOR(i,0,n-1) FOR(j,0,m-1) {
if (grid[i][j] == '#') {
hk.addEdge(h_id[i][j], v_id[i][j]);
}
}
// Kết quả = size của maximum matching = size của minimum vertex cover
cout << hk.maxMatching() << "\n";
}
int main() {
solve();
return 0;
}
