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>
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
Shining through the city with a little funk and soul
*/
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1404E
   {
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());
         char[][] grid = new char[N][M];
         for(int r=0; r < N; r++)
            grid[r] = infile.readLine().toCharArray();
         int[][] right = new int[N][M];
         int[][] down = new int[N][M];
         int id = 0;
         for(int r=0; r < N; r++)
         {
            for(int c=0; c < M-1; c++)
               right[r][c] = ++id;
            if(r+1 < N)
               for(int c=0; c < M; c++)
                  down[r][c] = ++id;
         }
         //source -> vertical -> horizontal -> sink
         int source = id+1;   int sink = id+2;
         MaxFlow flow = new MaxFlow(id+2, source, sink);
         HashSet<Integer> good = new HashSet<Integer>();
         for(int r=0; r < N; r++)
            for(int c=0; c < M-1; c++)
               if(grid[r][c] == '#' && grid[r][c+1] == '#')
               {
                  flow.addEdge(source, right[r][c], 1L);
                  good.add(right[r][c]);
               }
         for(int r=0; r < N-1; r++)
            for(int c=0; c < M; c++)
               if(grid[r][c] == '#' && grid[r+1][c] == '#')
               {
                  flow.addEdge(down[r][c], sink, 1L);
                  good.add(down[r][c]);
               }
         for(int r=0; r < N; r++)
            for(int c=0; c < M; c++)
               if(grid[r][c] == '#')
               {
                  if(r+1 < N && c+1 < M && grid[r+1][c] == '#' && grid[r][c+1] == '#')
                  {
                     if(good.contains(right[r][c]) && good.contains(down[r][c]))
                        flow.addEdge(right[r][c], down[r][c], Integer.MAX_VALUE);
                  }
                  if(r+1 < N && c-1 >= 0 && grid[r+1][c] == '#' && grid[r][c-1] == '#')
                  {
                     if(good.contains(right[r][c-1]) && good.contains(down[r][c]))
                        flow.addEdge(right[r][c-1], down[r][c], Integer.MAX_VALUE);
                  }
                  if(r-1 >= 0 && c+1 < M && grid[r-1][c] == '#' && grid[r][c+1] == '#')
                  {
                     if(good.contains(right[r][c]) && good.contains(down[r-1][c]))
                        flow.addEdge(right[r][c], down[r-1][c], Integer.MAX_VALUE);
                  }
                  if(r-1 >= 0 && c-1 >= 0 && grid[r-1][c] == '#' && grid[r][c-1] == '#')
                  {
                     if(good.contains(right[r][c-1]) && good.contains(down[r-1][c]))
                        flow.addEdge(right[r][c-1], down[r-1][c], Integer.MAX_VALUE);
                  }
               }
         int res = (int)flow.mfmc()-good.size();
         for(int r=0; r < N; r++)
            for(int c=0; c < M; c++)
               if(grid[r][c] == '#')
                  res++;
         System.out.println(res);
      }
   }
   class MaxFlow
   {
      public int N, source, sink;
      public ArrayList<Edge>[] edges;
      private int[] depth;
      
      public MaxFlow(int n, int x, int y)
      {
         N = n;
         source = x;
         sink = y;
         edges = new ArrayList[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new ArrayList<Edge>();
         depth = new int[N+1];
      }
      public void addEdge(int from, int to, long cap)
      {
         Edge forward = new Edge(from, to, cap);
         Edge backward = new Edge(to, from, 0L);
         forward.residual = backward;
         backward.residual = forward;
         edges[from].add(forward);
         edges[to].add(backward);
      }
      public long mfmc()
      {
         long res = 0L;
         int[] magic = new int[N+1];
         while(assignDepths())
         {
            long flow = dfs(source, Long.MAX_VALUE/2, magic);
            while(flow > 0)
            {
               res += flow;
               flow = dfs(source, Long.MAX_VALUE/2, magic);
            }
            magic = new int[N+1];
         }
         return res;
      }
      private boolean assignDepths()
      {
         Arrays.fill(depth, -69);
         ArrayDeque<Integer> q = new ArrayDeque<Integer>();
         q.add(source);
         depth[source] = 0;
         while(q.size() > 0)
         {
            int curr = q.poll();
            for(Edge e: edges[curr])
               if(e.capacityLeft() > 0 && depth[e.to] == -69)
               {
                  depth[e.to] = depth[curr]+1;
                  q.add(e.to);
               }
         }
         return depth[sink] != -69;
      }
      private long dfs(int curr, long bottleneck, int[] magic)
      {
         if(curr == sink)
            return bottleneck;
         for(; magic[curr] < edges[curr].size(); magic[curr]++)
         {
            Edge e = edges[curr].get(magic[curr]);
            if(e.capacityLeft() > 0 && depth[e.to]-depth[curr] == 1)
            {
               long val = dfs(e.to, Math.min(bottleneck, e.capacityLeft()), magic);
               if(val > 0)
               {
                  e.augment(val);
                  return val;
               }
            }
         }
         return 0L;  //no flow
      }
      private class Edge
      {
         public int from, to;
         public long flow, capacity;
         public Edge residual;
         
         public Edge(int f, int t, long cap)
         {
            from = f;
            to = t;
            capacity = cap;
         }
         public long capacityLeft()
         {
            return capacity-flow;
         }
         public void augment(long val)
         {
            flow += val;
            residual.flow -= val;
         }
      }
   }