1404_E. Bricks_28892
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;
int n, m;
int fi[80004], ne[80004 << 4], to[80004 << 4], c[80004 << 4], num = 1;
void add(int x, int y, int z) {
  ne[++num] = fi[x];
  fi[x] = num;
  to[num] = y;
  c[num] = z;
  ne[++num] = fi[y];
  fi[y] = num;
  to[num] = x;
  c[num] = 0;
}
int dep[80004], q[80004], l, r, s, t, ans;
int cur[80004];
bool bfs() {
  l = 1;
  r = 0;
  q[++r] = s;
  for (int i = 0; i <= t; i++) dep[i] = 0, cur[i] = fi[i];
  dep[s] = 1;
  while (l <= r) {
    int k = q[l++];
    for (int i = fi[k]; i; i = ne[i])
      if (c[i] && !dep[to[i]]) {
        dep[to[i]] = dep[k] + 1;
        q[++r] = to[i];
      }
  }
  return dep[t] != 0;
}
int dfs(int k, int fl) {
  if (k == t) {
    ans += fl;
    return fl;
  }
  int us = 0, fx;
  for (int i = cur[k]; i; i = ne[i]) {
    cur[k] = i;
    if (dep[to[i]] == dep[k] + 1 && c[i]) {
      if (fx = dfs(to[i], min(fl - us, c[i]))) {
        us += fx;
        c[i] -= fx;
        c[i ^ 1] += fx;
        if (us == fl) break;
      }
    }
  }
  return us;
}
void dinic() {
  while (bfs()) dfs(s, 0x3f3f3f3f);
}
int sum, cnt, v[80004];
char ss[202][202];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%s", ss[i] + 1);
  s = 0;
  t = n * m * 2 + 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (ss[i][j] == '#') {
        sum++;
        int uu = (i - 1) * m + j, rr = uu + n * m, dd = i * m + j, ll = rr - 1;
        if (ss[i - 1][j] == '#' && !v[uu]) ++cnt, v[uu] = 1, add(s, uu, 1);
        if (ss[i][j - 1] == '#' && !v[ll]) ++cnt, v[ll] = 1, add(ll, t, 1);
        if (ss[i - 1][j] == '#') {
          if (ss[i][j + 1] == '#') add(uu, rr, 1);
          if (ss[i][j - 1] == '#') add(uu, ll, 1);
        }
        if (ss[i + 1][j] == '#') {
          if (ss[i][j + 1] == '#') add(dd, rr, 1);
          if (ss[i][j - 1] == '#') add(dd, ll, 1);
        }
      }
  dinic();
  printf("%d", sum - (cnt - ans));
  return 0;
}

3 4
#.##
####
##..
 10 8
####..##
#..#.##.
#..#.###
####.#.#
....####
.###.###
###.#..#
########
###..###
.##.###.
 6 6
######
##....
######
##...#
##...#
######
 5 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#..#..#..##.#..#......#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
#.#...#..#..#..#..#..#..#..#..#......#..#..#..#..#...
#..#..####..#...#.####..#..#..#......####..#...#.####
 20 20
#.#.###..##.##..####
###.....####..###.##
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####.######
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
...#.##..#.##....###
#..###...###.####.##
##.#...##.#######.##
 1 200
#######..#####.#######.###########.#####.#.###############################.###.#######.###.###.##.#.##..##..#.###########.#.####.###.###.##################.##########.############.####..####.####.####
 13 15
..####...####..
.##..##.######.
##.############
##.############
##.############
.#############.
.#############.
..###########..
...#########...
....#######....
.....#####.....
......###......
.......#.......
 1 1
#
 1 200
#######..#####.#######.###########.#####.#.###############################.###.#######.###.###.##.#.##..##..#.###########.#.####.###.###.##################.##########.############.###$..####.####.####
 6 6
######
##....
######
.#..##
##...#
######
 20 20
#.#.###..##.##..####
###.....####..###.##
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####.######
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
###....##.#..##.#...
#..###...###.####.##
##.#...##.#######.##
 1 2
#
 5 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#.##..#..##.#.........#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
#.#...#..#..#..#..#..#..#..#..#......#..#..#..#..#...
#..#..####..#...#.####..#..#..#......####..#...#.####
 20 20
#.#.###..##.##..####
###.....####..###.##
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####.######
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
#..#..##.###..#.####
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
...#.##..#.##....###
#..###...###.####.##
##.#...##.#######.##
 10 8
####..##
.##.#..#
#..#.###
####.#.#
....####
.###.###
###.#..#
########
###..###
.##.###.
 5 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#.##..#..##.#.........#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
...#..#..#..#..#......#..#..#..#..#..#..#..#..#...#.#
#..#..####..#...#.####..#..#..#......####..#...#.####
 5 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#.##..#..##.#.........#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
...#..#..#..#..#......#..#..#..#..#..#..#..#..#...#.#
####.#...#..####......#..#..#..####.#...#..####..#..#
 5 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#.##..#..##.#....#.......#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
...#..#..#..#..#......#..#..#..#..#..#..#..#..#...#.#
####.#...#..####......#..#..#..####.#...#..####..#..#
 1 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#..#..#..##.#..#......#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
#.#...#..#..#..#..#..#..#..#..#......#..#..#..#..#...
#..#..####..#...#.####..#..#..#......####..#...#.####
 13 15
..####...####..
.##..##.######.
############.##
##.############
##.############
.#############.
.#############.
..###########..
...#########...
....#######....
.....#####.....
......###......
.......#.......
 10 8
####.##.
#..#.##.
#..#.###
####.#.#
....####
.###.###
###.#..#
########
###..###
.##.###.
 6 6
######
##....
######
##...#
##.#..
######
 20 20
#.#.###..##.##..####
###.....####..###.##
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####.######
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
#..#..##.###..#.####
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
...###...#.##....###
#..###...###.####.##
##.#...##.#######.##
 10 8
####..##
.##.#..#
#..#.###
####.#.#
....####
.###.###
####...#
########
###..###
.##.###.
 20 20
#.#.###..##.##..####
##.###..####.....###
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####."#####
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
###....##.#..##.#...
#..###...###.####.##
##.#######.##...#.##
 1 53
#..#..#..#..####..####..#..#..#.....#####..####..#.##
#.#...#..#..#..#.##..#..##.#.........#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
#.#...#..#..#..#..#..#..#..#..#......#..#..#..#..#...
#..#..####..#...#.##"#..#..#..#......####..#...#.####
 5 53
####..####..####......#..#..#..####..####..#..#..#..#
.#....#..#..#..#.........#.##..#..##.#..#..#..#...#.#
##....#..#..###...#..#..#.#...#......#..#..###..#.#..
...#..#..#..#..#......#..#..#..#..#..#..#..#..#...#.#
####.#...#..####......#..#..#..####.#...#..####..#..#
 3 53
####..####..####......#..#..#..####..####..#..#..#..#
.#....#..#..#..#.........#.##..#..##.#..#..#..#...#.#
##....#..#..###...#..#..#.#...#......#..#..###..#.#..
...#..#..#..#..#......#..#..#..#..#..#..#..#..#...#.#
####.#...#..####......#..#..#..####.#...#..####..#..#
 20 20
#.#.###..##.##..####
###.....####..###.##
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####."#####
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
###....##.#..##.#...
#..###...###.####.##
##.#...##.#######.##
 6 6
######
##....
######
.#..##
#...##
######
 20 20
#.#.###..##.##..####
##".....####..###.##
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####.######
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
###....##.#..##.#...
#..###...###.####.##
##.#...##.#######.##
 20 20
#.#.###..##.##..####
##.###..####.....###
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####."#####
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
###....##.#..##.#...
#..###...###.####.##
##.#...##.#######.##
 1 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#.##..#..##.#.........#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
#.#...#..#..#..#..#..#..#..#..#......#..#..#..#..#...
#..#..####..#...#.####..#..#..#......####..#...#.####
 5 53
#..#..#..#..####..####..#..#..#......####..####..####
.#....#..#..#..#.........#.##..#..##.#..#..#..#...#.#
##....#..#..###...#..#..#.##..#......#..#..###....#..
...#..#..#..#..#......#..#..#..#..#..#..#..#..#...#.#
####.#...#..####......#..#..#..####.#...#..####..#..#
 1 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#..#..#..##.#..#......#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#./#..###....#..
#.#...#..#..#..#..#..#..#..#..#......#..#..#..#..#...
#..#..####..#...#.####..#..#..#......####..#...#.####
 10 8
####.##.
#..#.##.
#..#.###
####.#.#
....####
.###.###
###.#..#
########
###..##$
.##.###.
 6 6
######
##....
######
##...#
##.#..
#####"
 20 20
#.#.###..##.##..####
##".....####..###.##
..####.#....#####.#.
####.#.#.##.#.#...##
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####.######
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
###....##.#..##.#...
#..###...###.####.##
##.#...##.#######.##
 1 53
#..#..#..#..####..####..#..#..#......####..####..####
#.#...#..#..#..#.##..#..##.#.........#..#..#..#....#.
##....#..#..###...#..#..#.##..#......#..#..###....#..
#.#...#..#..#..#..#..#..#..#..#......#..#..#..#..#...
#..#..####..#...#.##"#..#..#..#......####..#...#.####
 10 8
####..##
.##.#..#
#..#.###
####.#.#
....####
.###.###
####...#
########
###..###
.###.##.
 5 53
####..####..####......#..#..#..####..####..#..#..#..#
.#....#..#..#..#.........#.##..#..##.#..#..#..#...#.#
##....#..#..###...#..#..#.##..#......#..#..###....#..
...#..#..#..#..#......#..#..#..#..#..#..#..#..#...#.#
####.#...#..####......#..#..#..####.#...#..####..#..#
 6 6
######
##....
######
#...##
##.#..
#####"
 20 20
#.#.###..##.##..####
##.###..####.....###
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
##..#####.#.#.#####.
#####.##.####."#####
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
###....##.#..##.#...
#..###...###.###.###
##.#######.##...#.##
 10 8
####..##
.##.#..#
#..#.###
####.#.#
....####
.###.###
####-..#
########
###..###
.###.##.
 20 20
#.#.###..##.##..####
##.###..####.....###
..####.#....#####.#.
##...#.#.##.#.#.####
...#.#..###.#.##....
..#.##.#.##.#.##...#
#.#####..###.######.
.#####.#.#.#####..##
#####.##.####."#####
###.#.#.####...####.
##...#..#.....####.#
..#####.##.#..#.####
.#..##..##......###.
###.##.#...##.######
##.#..##.###..#..###
#.##.#...#.#.#.....#
.#.###.#....#.###.#.
###....##.#..##.#...
#..###...###.###.###
##.#######.##...#.##

4
 18
 6
 39
 89
 28
 17
 1
 28
 8
 92
 1
 41
 89
 20
 49
 46
 47
 12
 18
 17
 7
 87
 19
 91
 13
 48
 32
 92
 8
 92
 92
 12
 49
 12
 17
 7
 92
 12
 19
 47
 8
 92
 19
 91
