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;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
pi readpi(ll off = 0) {
  ll first, second;
  cin >> first >> second;
  return pi(first + off, second + off);
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
ll botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
ll mask(ll i) { return (ll(1) << i) - 1; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
void myshuffle(vc<t>& first) {
  for (ll i = ll(0); i < ll(ll(first.size())); i++)
    swap(first[i], first[rand_int(0, i)]);
}
template <class t>
ll lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
vvc<ll> readGraph(ll n, ll m) {
  vvc<ll> g(n);
  for (ll i = ll(0); i < ll(m); i++) {
    ll first, second;
    cin >> first >> second;
    first--;
    second--;
    g[first].push_back(second);
    g[second].push_back(first);
  }
  return g;
}
vvc<ll> readTree(ll n) { return readGraph(n, n - 1); }
template <class d>
struct maxflow {
  struct E {
    ll to, rev;
    d cap;
  };
  vvc<E> g;
  vi itr, lv, q;
  maxflow(ll n) : g(n), itr(n), lv(n), q(n) {}
  ll ae(ll s, ll t, d c) {
    g[s].push_back({t, (ll)g[t].size(), c});
    g[t].push_back({s, (ll)g[s].size() - 1, 0});
    return ll(g[s].size()) - 1;
  }
  void bfs(ll s) {
    fill(lv.begin(), lv.end(), -1);
    lv[s] = 0;
    ll l = 0, r = 0;
    q[r++] = s;
    while (l < r) {
      ll v = q[l++];
      for (auto e : g[v])
        if (e.cap > 0 && lv[e.to] == -1) {
          lv[e.to] = lv[v] + 1;
          q[r++] = e.to;
        }
    }
  }
  d dfs(ll v, ll t, d f) {
    if (v == t) return f;
    d res = 0;
    for (ll& i = itr[v]; i < (ll)g[v].size(); i++) {
      E& e = g[v][i];
      if (e.cap > 0 && lv[e.to] == lv[v] + 1) {
        d first = dfs(e.to, t, min(f, e.cap));
        if (first > 0) {
          e.cap -= first;
          g[e.to][e.rev].cap += first;
          res += first;
          f -= first;
          if (f <= 0) break;
        }
      }
    }
    return res;
  }
  d calc(ll s, ll t, d mx = inf) {
    d f = 0;
    while (f < mx) {
      bfs(s);
      if (lv[t] == -1) return f;
      fill(itr.begin(), itr.end(), 0);
      f += dfs(s, t, mx - f);
    }
    return f;
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  ll n, m;
  cin >> n >> m;
  vc<string> str(n);
  for (ll i = ll(0); i < ll(n); i++) cin >> str[i];
  vvc<ll> idx(n, vi(m, -1));
  ll s = 1;
  ll tot = 0;
  for (ll i = ll(0); i < ll(n); i++)
    for (ll j = ll(0); j < ll(m); j++)
      if (str[i][j] == '#') {
        idx[i][j] = s++;
        tot++;
      }
  maxflow<ll> mf(++s);
  ll ans = 0;
  for (ll i = ll(0); i < ll(n - 1); i++)
    for (ll j = ll(0); j < ll(m); j++)
      if (idx[i][j] != -1 && idx[i + 1][j] != -1) {
        ans += 2;
        mf.ae(0, idx[i][j], 1);
        mf.ae(0, idx[i + 1][j], 1);
        mf.ae(idx[i][j], idx[i + 1][j], 1);
        mf.ae(idx[i + 1][j], idx[i][j], 1);
      }
  for (ll i = ll(0); i < ll(n); i++)
    for (ll j = ll(0); j < ll(m - 1); j++)
      if (idx[i][j] != -1 && idx[i][j + 1] != -1) {
        ans += 2;
        mf.ae(idx[i][j], s - 1, 1);
        mf.ae(idx[i][j + 1], s - 1, 1);
        mf.ae(idx[i][j], idx[i][j + 1], 1);
        mf.ae(idx[i][j + 1], idx[i][j], 1);
      }
  ans -= mf.calc(0, s - 1);
  print(tot - ans / 2);
}
