Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.

The grid is said to be good if and only if the following condition is satisfied:

* From (1, 1), we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.



Note that (1, 1) and (H, W) must be white if the grid is good.

Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.

* Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) - that is, from white to black and vice versa.

Constraints

* 2 \leq H, W \leq 100

Input

Input is given from Standard Input in the following format:


H W
s_{11} s_{12} \cdots s_{1W}
s_{21} s_{22} \cdots s_{2W}
\vdots
s_{H1} s_{H2} \cdots s_{HW}


Here s_{rc} represents the color of (r, c) - `#` stands for black, and `.` stands for white.

Output

Print the minimum number of operations needed.

Examples

Input

3 3
.##
.#.
##.


Output

1


Input

3 3
.##
.#.
.


Output

1


Input

2 2
.
.#


Output

2


Input

4 4
..##
...
.
.


Output

0


Input

5 5
.#.#.
.#.#
.#.#.
.#.#
.#.#.


Output

4

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

import static java.lang.Double.parseDouble;
import static java.lang.Integer.min;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Math.abs;
import static java.lang.System.exit;

public class Main {

    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;

    int n, m, dp[][][];
    char g[][];

    int dfs(int i, int j, boolean prevIsBlack) {
        if (i == n || j == m) return n + m;
        if (i == n - 1 && j == m - 1) {
            if (g[i][j] == '#') {
                return prevIsBlack ? 0 : 1;
            }
            return 0;
        }
        if (dp[prevIsBlack ? 1 : 0][i][j] != -1) return dp[prevIsBlack ? 1 : 0][i][j];
        int ans = n + m;
        if (g[i][j] == '#') {
            if (prevIsBlack) {
                ans = min(ans, dfs(i + 1, j, true));
                ans = min(ans, dfs(i, j + 1, true));
            } else {
                ans = min(ans, 1 + dfs(i + 1, j, true));
                ans = min(ans, 1 + dfs(i, j + 1, true));
            }
        } else {
            ans = min(ans, dfs(i + 1, j, false));
            ans = min(ans, dfs(i, j + 1, false));
        }
        return dp[prevIsBlack ? 1 : 0][i][j] = ans;
    }

    void solve() throws Exception {
        n = nextInt();
        m = nextInt();
        g = new char[n][m];
        dp = new int[2][n][m];
        for (int i = 0; i < n; i++) {
            g[i] = next().toCharArray();
            Arrays.fill(dp[0][i], -1);
            Arrays.fill(dp[1][i], -1);
        }
        int ans1 = dfs(0, 0, false);
        int ans2 = 1 + n + m - 1 - ans1;
        int ans = min(ans1, ans2);
        out.println(ans);
    }


    // call it like this: lower_bound(a, x + 1) ( /!\ + 1 )
    public static int lower_bound(int[] a, int v) {
        int low = -1, high = a.length;
        while (high - low > 1) {
            int h = high + low >>> 1;
            if (a[h] >= v) {
                high = h;
            } else {
                low = h;
            }
        }
        return high;
    }

    private String getFraction(int a, int b) {
        assert b != 0;
        String sign = (a > 0 && b > 0) || (a < 0) && (b < 0) ? "+" : "-";
        a = abs(a);
        b = abs(b);
        int gcd = gcd(a, b);
        return sign + (a / gcd) + "/" + (b / gcd);
    }

    private int gcd(int a, int b) {
        while (b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private int lcm(int a, int b) {
        return a * (b / gcd(a, b));
    }

    public static int[] radixSort(int[] f) {
        if (f.length < 100) {
            Arrays.sort(f);
            return f;
        }
        int[] to = new int[f.length];
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++) b[1 + (f[i] & 0xffff)]++;
            for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++) to[b[f[i] & 0xffff]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++) b[1 + (f[i] >>> 16)]++;
            for (int i = 1; i <= 65536; i++) b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++) to[b[f[i] >>> 16]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        return f;
    }

    public static long pow(long a, long n, long mod) {
        long ret = 1;
        int x = 63 - Long.numberOfLeadingZeros(n);
        for (; x >= 0; x--) {
            ret = ret * ret % mod;
            if (n << 63 - x < 0)
                ret = ret * a % mod;
        }
        return ret;
    }

    class BIT {
        int BITree[];

        public BIT(int n) {
            BITree = new int[n + 1];
            for (int i = 1; i <= n; i++)
                BITree[i] = 0;
        }

        // sum [l, r]
        int getSum(int l, int r) {
            return getSum(r) - getSum(l - 1);
        }

        // sum [0, index]
        int getSum(int index) {
            int sum = 0;
            index = index + 1;
            while (index > 0) {
                sum += BITree[index];
                index -= index & (-index);
            }
            return sum;
        }

        // add val to range [l, r]
        void updateRange(int n, int val, int l, int r) {
            updateBIT(n, l, val);
            updateBIT(n, r + 1, -val);
        }

        void updateBIT(int n, int index, int val) {
            index = index + 1;
            while (index <= n) {
                BITree[index] += val;
                index += index & (-index);
            }
        }
    }

    public static boolean nextPermutation(Integer[] a) {
        int n = a.length;
        int i;
        for (i = n - 2; i >= 0 && a[i] >= a[i + 1]; i--) ;
        if (i == -1)
            return false;
        int j;
        for (j = i + 1; j < n && a[i] < a[j]; j++) ;
        int d = a[i];
        a[i] = a[j - 1];
        a[j - 1] = d;
        for (int p = i + 1, q = n - 1; p < q; p++, q--) {
            d = a[p];
            a[p] = a[q];
            a[q] = d;
        }
        return true;
    }

    void print(Object x) {
        out.print(String.valueOf(x));
        out.flush();
    }

    void println(Object x) {
        out.println(String.valueOf(x));
        out.flush();
    }

    private class MapCount<K> {
        Map<K, Integer> map;

        public MapCount() {
            map = new HashMap<>();
        }

        public void add(K key) {
            map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
        }

        public Integer getCount(K key) {
            return map.getOrDefault(key, 0);
        }
    }

    // for Map with custom key/value, override toString in your custom class
    void printMap(Map map) {
        if (map.keySet().size() == 0) return;
        Object firstValue = map.keySet().iterator().next();
        if (map.get(firstValue) instanceof Queue || map.get(firstValue) instanceof List) {
            for (Object key : map.keySet()) {
                out.print(String.valueOf(key) + ": ");
                Collection values = (Collection) map.get(key);
                for (Object value : values) out.print(String.valueOf(value) + " ");
                out.println();
            }
        } else if (map.get(firstValue).getClass().isArray()) {
            for (Object key : map.keySet()) {
                out.print(String.valueOf(key) + ": ");
                Object[] values = (Object[]) map.get(key);
                for (Object value : values) out.print(String.valueOf(value) + " ");
                out.println();
            }
        } else {
            for (Object key : map.keySet()) {
                out.println(String.valueOf(key) + ": " + map.get(key));
            }
        }
    }

    private int[] na(int n) throws IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = nextInt();
        return a;
    }

    private long[] nal(int n) throws IOException {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nextLong();
        return a;
    }

    int nextInt() throws IOException {
        return parseInt(next());
    }

    long nextLong() throws IOException {
        return parseLong(next());
    }

    double nextDouble() throws IOException {
        return parseDouble(next());
    }

    String next() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    public static void main(String[] args) throws Exception {
        try {
            boolean isLocal = false;
            if (isLocal) {
                in = new BufferedReader(new FileReader("solution.in"));
                out = new PrintWriter(new BufferedWriter(new FileWriter("solution.out")));
            } else {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }

            //long lStartTime = System.currentTimeMillis();
            new Main().solve();
            //long lEndTime = System.currentTimeMillis();
            //out.println("Elapsed time in seconds: " + (double)(lEndTime - lStartTime) / 1000.0);
            in.close();
            out.close();
        } catch (Throwable e) {
            e.printStackTrace();
            exit(1);
        }
    }
}