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;
long long const limLL = 9223372036854775807;
long long const dekai = 3e16;
const long double pi = acos(-1);
const char el = '\n';
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int ddx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int ddy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int mod = 1000000007;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (long long i = 0; i < (v.size()); i++) {
    if (i) os << " ";
    os << v[i];
  }
  return os;
}
template <typename T>
void view(const std::vector<T> &v) {
  std::cerr << "{ ";
  for (const auto &e : v) {
    std::cerr << e << ", ";
  }
  std::cerr << "\b\b }";
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv) {
  std::cerr << "{\n";
  for (const auto &v : vv) {
    std::cerr << "\t";
    view(v);
    cerr << "\n";
  }
  std::cerr << "}";
}
template <typename T, typename U>
void view(const std::vector<std::pair<T, U>> &v) {
  std::cerr << "{\n";
  for (const auto &c : v) {
    std::cerr << "\t(" << c.first << ", " << c.second << ")\n";
  }
  std::cerr << "}";
}
template <typename T, typename U>
void view(const std::map<T, U> &m) {
  std::cerr << "{\n";
  for (auto &t : m) {
    std::cerr << "\t[" << t.first << "] : " << t.second << "\n";
  }
  std::cerr << "}";
}
template <typename T, typename U>
void view(const std::pair<T, U> &p) {
  std::cerr << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
void view(const std::set<T> &s) {
  std::cerr << "{ ";
  for (auto &t : s) {
    view(t);
    std::cerr << ", ";
  }
  std::cerr << "\b\b }";
}
template <typename T>
void view(T e) {
  std::cerr << e;
}
template <class T = long long>
using V = vector<T>;
template <class T = long long>
using VV = V<V<T>>;
using P = pair<long long, long long>;
template <class T>
void scan(T a) {
  cin >> a;
}
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string &a) { cin >> a; }
template <class T>
void scan(V<T> &);
template <class T, class L>
void scan(pair<T, L> &);
template <class T>
void scan(V<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L> &p) {
  scan(p.first);
  scan(p.second);
}
template <class T>
void scan(T &a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
  scan(head);
  IN(tail...);
}
template <class T>
inline void print(T x) {
  cout << x << '\n';
}
template <class T>
V<T> press(V<T> &x) {
  V<T> res = x;
  sort((res).begin(), (res).end());
  res.erase(unique((res).begin(), (res).end()), res.end());
  for (int i = (0); i < (((int)(x).size())); ++i) {
    x[i] = lower_bound((res).begin(), (res).end(), x[i]) - res.begin();
  }
  return res;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
inline void Yes(bool b = true) { cout << (b ? "Yes" : "No") << '\n'; }
inline void YES(bool b = true) { cout << (b ? "YES" : "NO") << '\n'; }
inline void err(bool b = true) {
  if (b) {
    cout << -1 << '\n';
    exit(0);
  }
}
template <class T>
inline void fin(bool b = true, T e = 0) {
  if (b) {
    cout << e << '\n';
    exit(0);
  }
}
template <class T>
T divup(T x, T y) {
  return (x + (y - 1)) / y;
}
template <typename T>
T pow(T a, long long n, T e = 1) {
  T ret = e;
  while (n) {
    if (n & 1) ret *= a;
    a *= a;
    n >>= 1;
  }
  return ret;
}
const long long INF = 1e18;
template <typename flow_t>
struct Dinic {
 private:
  const flow_t INF = numeric_limits<flow_t>::max() / 10;
  struct edge {
    int to;
    flow_t cap;
    int rev;
    bool isrev;
    int idx;
  };
  VV<edge> graph;
  V<int> min_cost, iter;
  bool bfs(int s, int t) {
    min_cost.assign(((int)(graph).size()), -1);
    queue<int> que;
    min_cost[s] = 0;
    que.push(s);
    while (!que.empty() and min_cost[t] == -1) {
      int p = que.front();
      que.pop();
      for (auto &e : graph[p]) {
        if (e.cap > 0 and min_cost[e.to] == -1) {
          min_cost[e.to] = min_cost[p] + 1;
          que.push(e.to);
        }
      }
    }
    return min_cost[t] != -1;
  }
  flow_t dfs(int idx, const int t, flow_t flow) {
    if (idx == t) return flow;
    for (int &i = iter[idx]; i < ((int)(graph[idx]).size()); i++) {
      edge &e = graph[idx][i];
      if (e.cap > 0 and min_cost[idx] < min_cost[e.to]) {
        flow_t d = dfs(e.to, t, min(flow, e.cap));
        if (d > 0) {
          e.cap -= d;
          graph[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }

 public:
  Dinic(int v = 0) : graph(v) {}
  void add_edge(int from, int to, flow_t cap, int idx = -1) {
    graph[from].emplace_back(
        edge{to, cap, ((int)(graph[to]).size()), false, idx});
    graph[to].emplace_back(
        edge{from, 0, ((int)(graph[from]).size()) - 1, true, idx});
  }
  flow_t max_flow(int s, int t) {
    flow_t flow = 0;
    while (bfs(s, t)) {
      iter.assign(((int)(graph).size()), 0);
      flow_t f = 0;
      while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
    return flow;
  }
  void resize(int x) { graph.resize(x); }
  int size() { return ((int)(graph).size()); }
};
template <typename T>
struct ProjectSelectionProblem {
 private:
  int n;
  const T INF;
  T res = 0;
  Dinic<T> dinic;

 public:
  ProjectSelectionProblem(int n_) : n(n_), INF(numeric_limits<T>::max()) {
    dinic.resize(n + 2);
  }
  void x_and_noty_loss(int x, int y, T loss) {
    assert(loss >= 0);
    dinic.add_edge(x, y, loss);
  }
  void x_xor_y_loss(int x, int y, T loss) {
    x_and_noty_loss(x, y, loss);
    x_and_noty_loss(y, x, loss);
  }
  void x_get(int x, T get) {
    if (get < 0) {
      dinic.add_edge(x, n + 1, -get);
      return;
    }
    res += get;
    notx_loss(x, get);
  }
  void x_loss(int x, T loss) {
    if (loss < 0) {
      x_get(x, -loss);
      return;
    }
    dinic.add_edge(x, n + 1, loss);
  }
  void notx_get(int x, T get) {
    if (get < 0) {
      dinic.add_edge(n, x, -get);
      return;
    }
    res += get;
    x_loss(x, get);
  }
  void notx_loss(int x, T loss) {
    if (loss < 0) {
      notx_get(x, -loss);
      return;
    }
    dinic.add_edge(n, x, loss);
  }
  void x_and_y_get(int x, int y, T get) {
    assert(get >= 0);
    res += get;
    dinic.resize(dinic.size() + 1);
    int w = dinic.size() - 1;
    dinic.add_edge(n, w, get);
    dinic.add_edge(w, x, INF);
    dinic.add_edge(w, y, INF);
  }
  void x_nor_y_get(int x, int y, T get) {
    assert(get >= 0);
    res += get;
    dinic.resize(dinic.size() + 1);
    int w = dinic.size() - 1;
    dinic.add_edge(w, n + 1, get);
    dinic.add_edge(x, w, INF);
    dinic.add_edge(y, w, INF);
  }
  void x_equal_y_get(int x, int y, T get) {
    x_and_y_get(x, y, get);
    x_nor_y_get(x, y, get);
  }
  T solve() { return dinic.max_flow(n, n + 1) - res; }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(15);
  srand((unsigned)time(NULL));
  int n, m;
  IN(n, m);
  VV<char> c(n, V<char>(m));
  IN(c);
  auto conv = [&](int a, int b) { return a * m + b; };
  ProjectSelectionProblem<long long> psp(n * m);
  using vi = vector<int>;
  using vvi = vector<vi>;
  vvi a(n, vi(m));
  for (long long i = 0; i < (n); i++)
    for (long long j = 0; j < (m); j++) a[i][j] = (c[i][j] == '#');
  int sum = 0;
  for (long long i = 0; i < (n); i++)
    for (long long j = 0; j < (m); j++)
      if (a[i][j]) sum++;
  for (long long i = 0; i < (n - 1); i++)
    for (long long j = 0; j < (m); j++) {
      if (a[i][j] && a[i + 1][j]) {
        int k = conv(i, j), l = (conv(i + 1, j));
        psp.x_nor_y_get(k, l, 1);
      }
    }
  for (long long i = 0; i < (n); i++)
    for (long long j = 0; j < (m - 1); j++) {
      if (a[i][j] && a[i][j + 1]) {
        int k = conv(i, j), l = (conv(i, j + 1));
        psp.x_and_y_get(k, l, 1);
      }
    }
  sum += psp.solve();
  cout << sum << endl;
  return 0;
}
