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 = 1 << 30;
const long long linf = 1LL << 62;
const int MAX = 1020000;
long long dy[8] = {0, -1, 0, 1, 1, -1, 1, -1};
long long dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const double pi = acos(-1);
const double eps = 1e-7;
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T>
inline void print(T &a) {
  for (long long i = 0; i < (a.size()); i++) cout << a[i] << " ";
  cout << "\n";
}
template <typename T1, typename T2>
inline void print2(T1 a, T2 b) {
  cout << a << " " << b << "\n";
}
template <typename T1, typename T2, typename T3>
inline void print3(T1 a, T2 b, T3 c) {
  cout << a << " " << b << " " << c << "\n";
}
long long pcount(long long x) { return __builtin_popcountll(x); }
const long long mod = 1e9 + 7;
struct Dinic {
  struct edge {
    long long to, cap, rev;
  };
  vector<vector<edge>> G;
  vector<int> level, itr;
  long long n;
  const long long INF = 1 << 30;
  Dinic(long long n) : n(n) {
    G.resize(n);
    level.resize(n);
    itr.resize(n);
  }
  void add_edge(long long from, long long to, long long cap) {
    G[from].push_back({to, cap, (long long)G[to].size()});
    G[to].push_back({from, 0, (long long)G[from].size() - 1});
  }
  void bfs(int s) {
    fill(level.begin(), level.end(), -1);
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto &e : G[u]) {
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[u] + 1;
          q.push(e.to);
        }
      }
    }
  }
  long long dfs(int u, int t, long long f) {
    if (u == t) return f;
    for (int &i = itr[u]; i < G[u].size(); i++) {
      edge &e = G[u][i];
      if (e.cap > 0 && level[u] < level[e.to]) {
        long long 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;
  }
  long long max_flow(long long s, long long t) {
    long long flow = 0;
    while (1) {
      bfs(s);
      if (level[t] < 0) return flow;
      fill(itr.begin(), itr.end(), 0);
      long long f;
      while ((f = dfs(s, t, INF)) > 0) {
        flow += f;
      }
    }
  }
};
bool in(long long y, long long x, long long h, long long w) {
  return 0 <= y && y < h && 0 <= x && x < w;
}
void solve() {
  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  for (long long i = 0; i < (h); i++) cin >> s[i];
  Dinic flow(4 * h * w);
  int S = 4 * h * w - 2, T = 4 * h * w - 1;
  int W = 2 * w - 1;
  set<int> se;
  int cnt = 0;
  int edge = 0;
  auto add = [&](int from, int to, int cap = 1) {
    edge++;
    flow.add_edge(from, to, cap);
    if (!se.count(from)) flow.add_edge(S, from, cap);
    if (!se.count(to)) flow.add_edge(to, T, cap);
    se.insert(from);
    se.insert(to);
  };
  for (long long i = 0; i < (h); i++)
    for (long long j = 0; j < (w); j++)
      if (s[i][j] == '#') cnt++;
  for (long long i = 0; i < (h - 1); i++)
    for (long long j = 0; j < (w); j++) {
      if (s[i][j] == '.') continue;
      if (j + 1 < w) {
        if (s[i + 1][j] == '#' && s[i][j + 1] == '#') {
          int from = (2 * i + 1) * W + 2 * j, to = 2 * i * W + 2 * j + 1;
          add(from, to);
        }
        if (s[i + 1][j] == '#' && s[i + 1][j + 1] == '#') {
          int from = (2 * i + 1) * W + 2 * j, to = 2 * (i + 1) * W + 2 * j + 1;
          add(from, to);
        }
      }
      if (j > 0) {
        if (s[i + 1][j] == '#' && s[i + 1][j - 1] == '#') {
          int from = (2 * i + 1) * W + 2 * j, to = 2 * (i + 1) * W + 2 * j - 1;
          add(from, to);
        }
        if (s[i][j - 1] == '#' && s[i + 1][j] == '#') {
          int from = (2 * i + 1) * W + 2 * j, to = 2 * i * W + 2 * j - 1;
          add(from, to);
        }
      }
    }
  for (long long i = 0; i < (h); i++) {
    for (long long j = 0; j < (w); j++) {
      if (j + 1 < w && s[i][j] == '#' && s[i][j + 1] == '#') {
        se.insert(2 * i * W + 2 * j + 1);
      }
      if (i + 1 < h && s[i][j] == '#' && s[i + 1][j] == '#') {
        se.insert((2 * i + 1) * W + 2 * j);
      }
    }
  }
  cout << cnt - (se.size() - flow.max_flow(S, T)) << "\n";
}
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int t = 1;
  while (t--) {
    solve();
  }
}
