#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3000;

int N, M, K;
char S[MAXN+10][MAXN+10];
int A[MAXN+10][MAXN+10];

struct Edge
{
	int v, c, r;
};

vector<Edge> adj[MAXN+10];

void addEdge(int u, int v, int c)
{
	adj[u].push_back({v, c, adj[v].size()});
	adj[v].push_back({u, 0, adj[u].size()-1});
}

int lvl[MAXN+10];

bool bfs()
{
	queue<int> Q;
	for(int i=0; i<=K+K+1; i++) lvl[i]=0;
	lvl[0]=1;
	Q.push(0);
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		for(auto &[nxt, c, r] : adj[now])
		{
			if(lvl[nxt]) continue;
			if(!c) continue;
			Q.push(nxt);
			lvl[nxt]=lvl[now]+1;
		}
	}
	return lvl[K+K+1];
}

int pos[MAXN+10];

bool dfs(int now)
{
	if(now==K+K+1) return true;
	for(; pos[now]<adj[now].size(); pos[now]++)
	{
		auto &[nxt, c, r] = adj[now][pos[now]];
		if(!c) continue;
		if(lvl[nxt]!=lvl[now]+1) continue;
		if(dfs(nxt))
		{
			c=0;
			adj[nxt][r].c=1;
			return true;
		}
	}
	return false;
}

int X[MAXN+10];
vector<int> adj2[MAXN+10];

bool vis[MAXN+10];
void dfs2(int now)
{
	vis[now]=1;
	for(int nxt : adj2[now])
	{
		if(vis[nxt]) continue;
		dfs2(nxt);
	}
}

int ans;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) scanf(" %s", S[i]+1);

	int p=0, q=0;
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
	{
		if(S[i][j]=='#') continue;
		if((i+j)%2==0) A[i][j]=++p;
		else A[i][j]=++q;
	}
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) if(S[i][j]=='.' && (i+j)%2) A[i][j]+=p;
	assert(p==q);

	if(p>1000) return !printf("1000000\n");
	K=p;

	ans=K*(K-1);

	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			if(A[i][j]==0) continue;
			if(i+1<=N && A[i+1][j]!=0)
			{
				int u=A[i][j], v=A[i+1][j];
				if(u>v) swap(u, v);
				addEdge(u, v, 1);
			}
			if(j+1<=M && A[i][j+1]!=0)
			{
				int u=A[i][j], v=A[i][j+1];
				if(u>v) swap(u, v);
				addEdge(u, v, 1);
			}
		}
	}
	for(int i=1; i<=K; i++) addEdge(0, i, 1), addEdge(i+K, K+K+1, 1);

	while(bfs())
	{
		for(int i=0; i<=K+K+1; i++) pos[i]=0;
		while(dfs(0));
	}
	for(int i=K+1; i<=K+K; i++)
	{
		for(auto &[nxt, c, r] : adj[i])
		{
			if(nxt==K+K+1) continue;
			if(c==1) X[i]=nxt, X[nxt]=i;
		}
		for(auto &[nxt, c, r] : adj[i])
		{
			if(nxt==K+K+1) continue;
			if(c==0) adj2[X[i]].push_back(nxt);
		}
	}

	for(int i=1; i<=K; i++)
	{
		for(int j=1; j<=K; j++) vis[j]=0;
		dfs2(i);
		for(int j=1; j<=K; j++) if(!vis[j]) ans++;
	}

	ans=min(ans, 1000000);
	printf("%d\n", ans);
}