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>
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.util.ListIterator;
import java.util.ArrayList;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.List;
import java.util.stream.Stream;
import java.io.Closeable;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            EBricks solver = new EBricks();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class EBricks {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int m = in.readInt();
            char[][] mat = new char[n][m];
            for (int i = 0; i < n; i++) {
                in.readString(mat[i], 0);
            }

            int down = 0;
            int right = 1;
            int[][][] id = new int[2][n][m];
            int lrId = 0;
            int udId = 0;
            SequenceUtils.deepFill(id, -1);
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (mat[i][j] == '.') {
                        continue;
                    }
                    cnt++;
                    if (i + 1 < n && mat[i + 1][j] == '#') {
                        id[down][i][j] = udId++;
                    }
                    if (j + 1 < m && mat[i][j + 1] == '#') {
                        id[right][i][j] = lrId++;
                    }
                }
            }

            DinicBipartiteMatch bm = new DinicBipartiteMatch(lrId, udId);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (id[right][i][j] == -1) {
                        continue;
                    }
                    for (int dx = 0; dx >= -1; dx--) {
                        for (int dy = 0; dy <= 1; dy++) {
                            int x = dx + i;
                            int y = dy + j;
                            if (x < 0 || x >= n || y < 0 || y >= m) {
                                continue;
                            }
                            if (id[down][x][y] == -1) {
                                continue;
                            }
                            bm.addEdge(id[right][i][j], id[down][x][y]);
                        }
                    }
                }
            }

            int maxMatch = bm.solve();
            int maxIndependentSet = lrId + udId - maxMatch;
            int ans = cnt - maxIndependentSet;
            out.println(ans);
        }

    }

    static class IntegerDinic implements IntegerMaximumFlow {
        List<IntegerFlowEdge>[] g;
        int s;
        int t;
        IntegerDeque deque;
        int[] dists;
        ListIterator<IntegerFlowEdge>[] iterators;

        public IntegerDinic() {
        }

        public void ensure(int vertexNum) {
            if (dists != null && dists.length >= vertexNum) {
                return;
            }
            deque = new IntegerDequeImpl(vertexNum);
            dists = new int[vertexNum];
            iterators = new ListIterator[vertexNum];
        }

        public int send(int root, int flow) {
            if (root == t) {
                return flow;
            }
            int snapshot = flow;
            while (iterators[root].hasNext()) {
                IntegerFlowEdge e = iterators[root].next();
                int remain;
                if (dists[e.to] + 1 != dists[root] || (remain = e.rev.flow) == 0) {
                    continue;
                }
                int sent = send(e.to, Math.min(flow, remain));
                flow -= sent;
                IntegerFlow.send(e, sent);
                if (flow == 0) {
                    iterators[root].previous();
                    break;
                }
            }
            return snapshot - flow;
        }

        public int apply(List<IntegerFlowEdge>[] g, int s, int t, int send) {
            ensure(g.length);
            this.s = s;
            this.t = t;
            this.g = g;
            int flow = 0;
            while (flow < send) {
                IntegerFlow.bfsForFlow(g, t, dists, Integer.MAX_VALUE, deque);
                if (dists[s] == Integer.MAX_VALUE) {
                    break;
                }
                for (int i = 0; i < g.length; i++) {
                    iterators[i] = g[i].listIterator();
                }
                flow += send(s, send - flow);
            }
            return flow;
        }

    }

    static class DinicBipartiteMatch {
        private List<IntegerFlowEdge>[] g;
        private IntegerDinic dinic;
        private int[] lMates;
        private int[] rMates;
        int l;
        int r;

        private int idOfL(int i) {
            return i;
        }

        private int idOfR(int i) {
            return i + l;
        }

        private int idOfSrc() {
            return l + r;
        }

        private int idOfDst() {
            return idOfSrc() + 1;
        }

        public DinicBipartiteMatch(int l, int r) {
            this.l = l;
            this.r = r;
            lMates = new int[l];
            rMates = new int[r];
            g = IntegerFlow.createFlow(idOfDst() + 1);
            dinic = new IntegerDinic();
            for (int i = 0; i < l; i++) {
                IntegerFlow.addEdge(g, idOfSrc(), idOfL(i), 1);
            }
            for (int i = 0; i < r; i++) {
                IntegerFlow.addEdge(g, idOfR(i), idOfDst(), 1);
            }
        }

        public void addEdge(int u, int v) {
            IntegerFlow.addEdge(g, idOfL(u), idOfR(v), 1);
        }

        public int solve() {
            Arrays.fill(lMates, -1);
            Arrays.fill(rMates, -1);
            dinic.apply(g, idOfSrc(), idOfDst(), l);
            int ans = 0;
            for (int i = 0; i < l; i++) {
                for (IntegerFlowEdge e : g[idOfL(i)]) {
                    if (e.real && e.flow == 1) {
                        ans++;
                        int to = e.to - idOfR(0);
                        lMates[i] = to;
                        rMates[to] = i;
                        break;
                    }
                }
            }
            return ans;
        }

    }

    static class SequenceUtils {
        public static void deepFill(Object array, int val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof int[]) {
                int[] intArray = (int[]) array;
                Arrays.fill(intArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

    }

    static interface IntegerMaximumFlow {
    }

    static interface IntegerStack {
        void addLast(int x);

        boolean isEmpty();

        void clear();

    }

    static class IntegerDequeImpl implements IntegerDeque {
        private int[] data;
        private int bpos;
        private int epos;
        private static final int[] EMPTY = new int[0];
        private int n;

        public IntegerDequeImpl(int cap) {
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
            bpos = 0;
            epos = 0;
            n = cap;
        }

        private void expandSpace(int len) {
            while (n < len) {
                n = Math.max(n + 10, n * 2);
            }
            int[] newData = new int[n];
            if (bpos <= epos) {
                if (bpos < epos) {
                    System.arraycopy(data, bpos, newData, 0, epos - bpos);
                }
            } else {
                System.arraycopy(data, bpos, newData, 0, data.length - bpos);
                System.arraycopy(data, 0, newData, data.length - bpos, epos);
            }
            epos = size();
            bpos = 0;
            data = newData;
        }

        public IntegerIterator iterator() {
            return new IntegerIterator() {
                int index = bpos;


                public boolean hasNext() {
                    return index != epos;
                }


                public int next() {
                    int ans = data[index];
                    index = IntegerDequeImpl.this.next(index);
                    return ans;
                }
            };
        }

        public int removeFirst() {
            int ans = data[bpos];
            bpos = next(bpos);
            return ans;
        }

        public void addLast(int x) {
            ensureMore();
            data[epos] = x;
            epos = next(epos);
        }

        public void clear() {
            bpos = epos = 0;
        }

        private int next(int x) {
            return x + 1 >= n ? 0 : x + 1;
        }

        private void ensureMore() {
            if (next(epos) == bpos) {
                expandSpace(n + 1);
            }
        }

        public int size() {
            int ans = epos - bpos;
            if (ans < 0) {
                ans += data.length;
            }
            return ans;
        }

        public boolean isEmpty() {
            return bpos == epos;
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (IntegerIterator iterator = iterator(); iterator.hasNext(); ) {
                builder.append(iterator.next()).append(' ');
            }
            return builder.toString();
        }

    }

    static interface IntegerIterator {
        boolean hasNext();

        int next();

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class DirectedEdge {
        public int to;

        public DirectedEdge(int to) {
            this.to = to;
        }

        public String toString() {
            return "->" + to;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

    }

    static interface IntegerDeque extends IntegerStack {
        int removeFirst();

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static boolean equal(int a, int b) {
            return a == b;
        }

    }

    static class IntegerFlow {
        public static <T extends IntegerFlowEdge> void send(T edge, int flow) {
            edge.flow += flow;
            edge.rev.flow -= flow;
        }

        public static IntegerFlowEdge addEdge(List<IntegerFlowEdge>[] g, int s, int t, int cap) {
            IntegerFlowEdge real = new IntegerFlowEdge(t, 0, true);
            IntegerFlowEdge virtual = new IntegerFlowEdge(s, cap, false);
            real.rev = virtual;
            virtual.rev = real;
            g[s].add(real);
            g[t].add(virtual);
            return real;
        }

        public static List<IntegerFlowEdge>[] createFlow(int n) {
            return createGraph(n);
        }

        private static List[] createGraph(int n) {
            return IntStream.range(0, n).mapToObj(i -> new ArrayList<>()).toArray(i -> new List[i]);
        }

        public static <T extends IntegerFlowEdge> void bfsForFlow(List<T>[] g, int s, int[] dist, int inf, IntegerDeque deque) {
            Arrays.fill(dist, 0, g.length, inf);
            dist[s] = 0;
            deque.clear();
            deque.addLast(s);
            while (!deque.isEmpty()) {
                int head = deque.removeFirst();
                for (T e : g[head]) {
                    if (!DigitUtils.equal(e.flow, 0) && dist[e.to] == inf) {
                        dist[e.to] = dist[head] + 1;
                        deque.addLast(e.to);
                    }
                }
            }
        }

    }

    static class IntegerFlowEdge<T extends IntegerFlowEdge<T>> extends DirectedEdge {
        public int flow;
        public boolean real;
        public T rev;

        public IntegerFlowEdge(int to, int flow, boolean real) {
            super(to);
            this.flow = flow;
            this.real = real;
        }

        public String toString() {
            return rev.to + "-[" + flow + "/" + (flow + rev.flow) + "]->" + to;
        }

    }
}

