A brick is defined as a rectangle with integer side lengths with either width 1 or height 1 (or both).

There is an n× m grid, and each cell is colored either black or white. A tiling is a way to place bricks onto the grid such that each black cell is covered by exactly one brick, and each white cell is not covered by any brick. In other words, bricks are placed on black cells only, cover all black cells, and no two bricks overlap.

<image> An example tiling of the first test case using 5 bricks. It is possible to do better, using only 4 bricks. 

What is the minimum number of bricks required to make a valid tiling?

Input

The first line contains two integers n, m (1≤ n, m≤ 200) — the number of rows and columns, respectively.

The next n lines describe the grid. The i-th of these lines contains a string of length m, where the j-th character denotes the color of the cell in row i, column j. A black cell is given by "#", and a white cell is given by ".".

It is guaranteed that there is at least one black cell.

Output

Output a single integer, the minimum number of bricks required.

Examples

Input


3 4
#.##
####
##..


Output


4


Input


6 6
######
##....
######
##...#
##...#
######


Output


6


Input


10 8
####..##
#..#.##.
#..#.###
####.#.#
....####
.###.###
###.#..#
########
###..###
.##.###.


Output


18

Note

The first test case can be tiled with 4 bricks placed vertically.

The third test case can be tiled with 18 bricks like this:

<image>
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 3e5 + 7;
const long long LINF = 0x3f3f3f3f3f3f3f3f, MOD = 1e9 + 7;
const double Pi = acos(-1), EPS = 1e-6;
void test() { cerr << "\n"; }
template <typename T, typename... Args>
void test(T x, Args... args) {
  cerr << x << " ";
  test(args...);
}
inline long long qpow(long long a, long long b) {
  return b ? ((b & 1) ? a * qpow(a * a % MOD, b >> 1) % MOD
                      : qpow(a * a % MOD, b >> 1)) %
                 MOD
           : 1;
}
inline long long qpow(long long a, long long b, long long c) {
  return b ? ((b & 1) ? a * qpow(a * a % c, b >> 1, c) % c
                      : qpow(a * a % c, b >> 1, c)) %
                 c
           : 1;
}
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long cede(long long a, long long b) {
  if (b < 0) return cede(-a, -b);
  if (a < 0) return a / b;
  return (a + b - 1) / b;
}
inline long long flde(long long a, long long b) {
  if (b < 0) return flde(-a, -b);
  if (a < 0) return (a - b + 1) / b;
  return a / b;
}
inline int sign(double x) { return x < -EPS ? -1 : x > EPS; }
inline int dbcmp(double l, double r) { return sign(l - r); }
namespace Fast_IO {
const int MAXL((1 << 18) + 1);
int iof, iotp;
char ioif[MAXL], *ioiS, *ioiT, ioof[MAXL],
    *iooS = ioof, *iooT = ioof + MAXL - 1, ioc, iost[55];
char Getchar() {
  if (ioiS == ioiT) {
    ioiS = ioif;
    ioiT = ioiS + fread(ioif, 1, MAXL, stdin);
    return (ioiS == ioiT ? EOF : *ioiS++);
  } else
    return (*ioiS++);
}
void Write() {
  fwrite(ioof, 1, iooS - ioof, stdout);
  iooS = ioof;
}
void Putchar(char x) {
  *iooS++ = x;
  if (iooS == iooT) Write();
}
inline int read() {
  int x = 0;
  for (iof = 1, ioc = Getchar(); (ioc < '0' || ioc > '9') && ioc != EOF;)
    iof = ioc == '-' ? -1 : 1, ioc = Getchar();
  if (ioc == EOF) exit(0);
  for (x = 0; ioc <= '9' && ioc >= '0'; ioc = Getchar())
    x = (x << 3) + (x << 1) + (ioc ^ 48);
  return x * iof;
}
inline long long read_ll() {
  long long x = 0;
  for (iof = 1, ioc = Getchar(); (ioc < '0' || ioc > '9') && ioc != EOF;)
    iof = ioc == '-' ? -1 : 1, ioc = Getchar();
  if (ioc == EOF) exit(0);
  for (x = 0; ioc <= '9' && ioc >= '0'; ioc = Getchar())
    x = (x << 3) + (x << 1) + (ioc ^ 48);
  return x * iof;
}
template <class Int>
void Print(Int x, char ch = '\0') {
  if (!x) Putchar('0');
  if (x < 0) Putchar('-'), x = -x;
  while (x) iost[++iotp] = x % 10 + '0', x /= 10;
  while (iotp) Putchar(iost[iotp--]);
  if (ch) Putchar(ch);
}
void Getstr(char *s, int &l) {
  for (ioc = Getchar(); ioc == ' ' || ioc == '\n' || ioc == '\t';)
    ioc = Getchar();
  if (ioc == EOF) exit(0);
  for (l = 0; !(ioc == ' ' || ioc == '\n' || ioc == '\t' || ioc == EOF);
       ioc = Getchar())
    s[l++] = ioc;
  s[l] = 0;
}
void Putstr(const char *s) {
  for (int i = 0, n = strlen(s); i < n; ++i) Putchar(s[i]);
}
}  // namespace Fast_IO
using namespace Fast_IO;
const int MAXG = 3e5 + 50;
struct Edge {
  int from, to;
  long long cost;
  int nxt;
};
struct Graph {
  struct Edge E[MAXG * 10];
  int cntE, head[MAXG];
  void init(int n = MAXG - 10) {
    if (n > MAXG / 2)
      memset(head, -1, sizeof(head));
    else
      for (int i = 0; i < n + 9; i++) head[i] = -1;
    cntE = 0;
  }
  void addE(int a, int b, long long c = 0) {
    E[cntE] = {a, b, c, head[a]};
    head[a] = cntE++;
  }
};
struct Dijkstra : Graph {
  long long dist[MAXG];
  struct DNode {
    long long val;
    int id;
    bool operator<(const DNode &r) const { return val > r.val; }
  };
  void Init(int n = MAXG - 100) {
    n *= 2;
    if (n > MAXG / 2)
      memset(dist, 0x3f, sizeof(dist));
    else
      for (int i = 0; i < n + 9; i++) dist[i] = 0x3f3f3f3f;
  }
  void Get_Dist(int s) {
    Init();
    priority_queue<DNode> pq;
    pq.push({0, s});
    dist[s] = 0;
    while (!pq.empty()) {
      DNode tmp = pq.top();
      pq.pop();
      if (tmp.val > dist[tmp.id]) continue;
      for (int i = head[tmp.id]; i != -1; i = E[i].nxt) {
        if (dist[E[i].to] > dist[tmp.id] + E[i].cost) {
          dist[E[i].to] = dist[tmp.id] + E[i].cost;
          pq.push({dist[E[i].to], E[i].to});
        }
      }
    }
  }
  int Get_Dist(int s, int t) {
    if (dist[t] == 0x3f3f3f3f && dist[s] != 0) Get_Dist(s);
    return dist[t];
  }
};
struct Dinic : Graph {
  int curE[MAXG], s, t, dist[MAXG];
  long long dfs(int u, long long f) {
    if (u == t) return f;
    long long ans = 0;
    for (int &i = curE[u]; i != -1; i = E[i].nxt) {
      if (dist[E[i].to] == dist[u] + 1 && E[i].cost > 0) {
        long long tmp = dfs(E[i].to, min(f, E[i].cost));
        f -= tmp;
        E[i].cost -= tmp;
        ans += tmp;
        E[i ^ 1].cost += tmp;
        if (!f) break;
      }
    }
    if (!ans) dist[u] = -1;
    return ans;
  }
  bool bfs(int n) {
    if (n > MAXG / 2)
      memset(dist, -1, sizeof(dist));
    else
      for (int i = 0; i < n + 9; i++) dist[i] = -1;
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int i = head[u]; i != -1; i = E[i].nxt) {
        if (dist[E[i].to] == -1 && E[i].cost > 0) {
          dist[E[i].to] = dist[u] + 1;
          q.push(E[i].to);
        }
      }
    }
    return dist[t] != -1;
  }
  long long dinic(int x, int y, int n) {
    s = x;
    t = y;
    long long ans = 0;
    while (bfs(n)) {
      for (int i = 0; i <= n; i++) curE[i] = head[i];
      ans += dfs(s, INF);
    }
    return ans;
  }
} din;
struct SCC : Graph {
  int DFN[MAXG], LOW[MAXG], tim, stk[MAXG], stktop, Scc[MAXG], Scc_Cnt;
  bool in_stk[MAXG];
  void Init(int n = MAXG - 10) {
    init(n);
    Scc_Cnt = tim = stktop = 0;
    if (n > MAXG / 2)
      memset(DFN, 0, sizeof(DFN)), memset(Scc, 0, sizeof(Scc)),
          memset(LOW, 0, sizeof(LOW)), memset(in_stk, 0, sizeof(in_stk));
    else
      for (int i = 0; i < n + 9; i++) DFN[i] = LOW[i] = Scc[i] = in_stk[i] = 0;
  }
  void dfs(int u) {
    DFN[u] = LOW[u] = ++tim;
    stk[++stktop] = u;
    in_stk[u] = 1;
    for (int i = head[u]; i != -1; i = E[i].nxt) {
      if (!DFN[E[i].to]) {
        dfs(E[i].to);
        LOW[u] = min(LOW[u], LOW[E[i].to]);
      } else if (in_stk[E[i].to])
        LOW[u] = min(LOW[u], LOW[E[i].to]);
    }
    if (DFN[u] == LOW[u]) {
      int x;
      Scc_Cnt++;
      do {
        x = stk[stktop--];
        in_stk[x] = 0;
        Scc[x] = Scc_Cnt;
      } while (x != u);
    }
  }
};
struct BCC : Graph {
  int DFN[MAXG], LOW[MAXG], tim, stk[MAXG], stktop, Bcc[MAXG], Bcc_Cnt;
  bool in_stk[MAXG];
  void Init(int n = MAXG - 10) {
    init(n);
    Bcc_Cnt = tim = stktop = 0;
    if (n > MAXG / 2)
      memset(DFN, 0, sizeof(DFN)), memset(Bcc, 0, sizeof(Bcc)),
          memset(LOW, 0, sizeof(LOW)), memset(in_stk, 0, sizeof(in_stk));
    else
      for (int i = 0; i < n + 9; i++) DFN[i] = LOW[i] = Bcc[i] = in_stk[i] = 0;
  }
  void dfs(int u, int fa = -1) {
    DFN[u] = LOW[u] = ++tim;
    stk[++stktop] = u;
    in_stk[u] = 1;
    for (int i = head[u]; i != -1; i = E[i].nxt) {
      if ((i ^ 1) == fa) continue;
      if (!DFN[E[i].to]) {
        dfs(E[i].to, i);
        LOW[u] = min(LOW[u], LOW[E[i].to]);
        if (LOW[E[i].to] > DFN[u]) {
          E[i].cost = 1;
          E[i ^ 1].cost = 1;
        }
      } else if (DFN[E[i].to] < DFN[u])
        LOW[u] = min(LOW[u], DFN[E[i].to]);
    }
    if (DFN[u] == LOW[u]) {
      int x;
      Bcc_Cnt++;
      do {
        x = stk[stktop--];
        in_stk[x] = 0;
        Bcc[x] = Bcc_Cnt;
      } while (x != u);
    }
  }
};
char str[222][222];
int mp[222][222];
void work() {
  int n = read(), m = read();
  int cntH = 0, cntV = 0;
  din.init();
  int tot = 0, cntn = 2;
  int S = 1, T = 2;
  int QAQ = 0;
  for (int i = 1; i <= n; i++) {
    int ttmp;
    Getstr(str[i] + 1, ttmp);
    for (int j = 1; j <= m; j++) {
      if (str[i][j] == '.') continue;
      tot++;
      if (str[i][j - 1] == '#') {
        QAQ++;
        int now = ++cntn;
        din.addE(S, now, 1);
        din.addE(now, S, 0);
        if (!mp[i][j - 1]) mp[i][j - 1] = ++cntn;
        if (!mp[i][j]) mp[i][j] = ++cntn;
        din.addE(now, mp[i][j - 1], INF);
        din.addE(mp[i][j - 1], now, 0);
        din.addE(now, mp[i][j], INF);
        din.addE(mp[i][j], now, 0);
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (str[j][i] == '.') continue;
      if (str[j - 1][i] == '#') {
        QAQ++;
        int now = ++cntn;
        din.addE(now, T, 1);
        din.addE(T, now, 0);
        if (!mp[j - 1][i]) mp[j - 1][i] = ++cntn;
        if (!mp[j][i]) mp[j][i] = ++cntn;
        din.addE(mp[j - 1][i], now, INF);
        din.addE(now, mp[j - 1][i], 0);
        din.addE(mp[j][i], now, INF);
        din.addE(now, mp[j][i], 0);
      }
    }
  }
  printf("%d\n", tot - QAQ + din.dinic(S, T, cntn + 1));
}
int main() { work(); }
