#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF INT_MAX/3
#define mod 1000000007
#define MAX_V 2000

struct edge{ int to,cap,rev; };
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,(int)G[to].size()});
  G[to].push_back((edge){from,0,(int)G[from].size()-1});
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    int v=que.front(); que.pop();
    for(int i=0;i<(int)G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[e.to]<0){
        level[e.to]=level[v]+1;
        que.push(e.to);
      }
    }
  }
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  for(int &i=iter[v];i<(int)G[v].size();i++){
    edge &e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow=0;
  while(1){
    bfs(s);
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f=dfs(s,t,INF))>0){
      flow+=f;
    }
  }
}

int R,C;
string s[25];
int prof=0,cnt=0;;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin>>R>>C;
  rep(i,R){
    cin>>s[i];
    rep(j,C)if(s[i][j]=='#')cnt++;
  }

  int source=2*R*C,sink=2*R*C+1;
  rep(i,R)rep(j,C){
    if(i<R-1&&s[i][j]=='#'&&s[i+1][j]=='#'){
      add_edge(source,i*C+j,1);
      add_edge(i*C+j,i*C+j+R*C,INF);
      add_edge(i*C+j,i*C+j-1+R*C,INF);
      add_edge(i*C+j,(i+1)*C+j-1+R*C,INF);
      add_edge(i*C+j,(i+1)*C+j+R*C,INF);
      prof++;
    }
    if(j<C-1&&s[i][j]=='#'&&s[i][j+1]=='#'){
      add_edge(i*C+j+R*C,sink,1);
      prof++;
    }
  }
  prof-=max_flow(source,sink);
  cout<<cnt-prof<<endl;

  return 0;
}


### Prompt

Construct a Cpp code solution to the problem outlined:

problem

Given the squares of $ R * C $. Each square is either an empty square or a square with a hole. The given square meets the following conditions.

* The cells with holes are connected. (You can move a square with a hole in the cross direction to any square with a hole)
* Empty cells are connected.



You can generate rectangular tiles of any length with a width of $ 1 $. I would like to install multiple tiles to fill all the holes in the square. When installing tiles, the following restrictions must be observed.

* Tiles can only be installed vertically or horizontally in the $ 2 $ direction.
* Do not install more than one tile on one square.
* There should be no tiles on the squares without holes.



Please answer the minimum number of tiles when all the squares with holes are filled with tiles while observing the above restrictions.



output

Output the minimum number of times. Please also output a line break at the end.

Example

Input

5 5
.....
.#.#.
.###.
.#.#.
.....


Output

3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF INT_MAX/3
#define mod 1000000007
#define MAX_V 2000

struct edge{ int to,cap,rev; };
vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,(int)G[to].size()});
  G[to].push_back((edge){from,0,(int)G[from].size()-1});
}

void bfs(int s){
  memset(level,-1,sizeof(level));
  queue<int> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    int v=que.front(); que.pop();
    for(int i=0;i<(int)G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[e.to]<0){
        level[e.to]=level[v]+1;
        que.push(e.to);
      }
    }
  }
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  for(int &i=iter[v];i<(int)G[v].size();i++){
    edge &e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow=0;
  while(1){
    bfs(s);
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    int f;
    while((f=dfs(s,t,INF))>0){
      flow+=f;
    }
  }
}

int R,C;
string s[25];
int prof=0,cnt=0;;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin>>R>>C;
  rep(i,R){
    cin>>s[i];
    rep(j,C)if(s[i][j]=='#')cnt++;
  }

  int source=2*R*C,sink=2*R*C+1;
  rep(i,R)rep(j,C){
    if(i<R-1&&s[i][j]=='#'&&s[i+1][j]=='#'){
      add_edge(source,i*C+j,1);
      add_edge(i*C+j,i*C+j+R*C,INF);
      add_edge(i*C+j,i*C+j-1+R*C,INF);
      add_edge(i*C+j,(i+1)*C+j-1+R*C,INF);
      add_edge(i*C+j,(i+1)*C+j+R*C,INF);
      prof++;
    }
    if(j<C-1&&s[i][j]=='#'&&s[i][j+1]=='#'){
      add_edge(i*C+j+R*C,sink,1);
      prof++;
    }
  }
  prof-=max_flow(source,sink);
  cout<<cnt-prof<<endl;

  return 0;
}


```