Given an $n \times m$ grid where each cell is either empty (.) or blocked (*), place the minimum number of $1 \times 2$ or $2 \times 1$ dominoes such that no two adjacent empty cells remain — i.e., it's impossible to place any additional domino.

Constraints: $1 \leq n \leq 70$, $1 \leq m \leq 7$.

Due to the small value of $m$, a dynamic programming approach with state compression per row is suitable. Each cell in the final configuration can be in one of three states:

• 0: empty (not covered by any domino)
• 1: part of a horizontal domino ($1 \times 2$) or the top half of a vertical domino ($2 \times 1$)
• 2: bottom half of a vertical domino

Note that originla obstacles must remain as obstacles and cannot be covered. To simplify, we assign obstacle cells the same encoding as state 1, since they are never empty and their exact role doesn't affect transitions beyond being non-empty.

The DP state is defined as $dp[i][s]$: the minimum number of domino-covered cells in the first $i$ rows, where row $i$ has ternary state $s$. The answer will be half this value (since each domino covers two cells).

Key validity conditions:

• No two horizontally adjacent cells in the same row can both be empty (state 0).
• No two vertically adjacent cells across consecutive rows can both be empty.
• State 2 (bottom of vertical domino) in row $i$ must align with state 1 (top) in row $i-1$.
• In any row, all state-1 cells not paired vertically must form even-length horizontal segments (to be fully covered by horizontal dominoes).
• Row 1 cannot contain state 2; row $n$ cannot have unpaired horizontal domino halves.

To optimize, precompute all valid row states (those without adjacent 0s). For $m=7$, this reduces the state space from $3^7 = 2187$ to 1224 states.

Further, precompute allowed transitions between pairs of valid states that satisfy vertical constraints (no vertical 0-0, and proper 1-2 alignment). This reduces possible transitions from ~1.5 million to ~129k for $m=7$.

During DP, for each candidate previous state, skip if it cannot improve the current DP value. Also, defer full validation of horizontal domino pairing until necessary, using early termination on invalid conditions.

The final implementation uses aggressive compiler optimizations and careful loop ordering to meet the tight 250ms time limit.

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX_N = 70, MAX_M = 7;

int n, m;
char grid[MAX_N + 1][MAX_M + 5];
vector<int> valid_states;
vector<vector<int>> digits;
vector<vector<int>> transitions;
vector<int> dp[MAX_N + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> grid[i];

    int pow3 = 1;
    for (int i = 0; i < m; i++) pow3 *= 3;

    // Precompute all row states without adjacent zeros
    vector<int> temp_digits(m);
    for (int mask = 0; mask < pow3; mask++) {
        int x = mask;
        for (int j = 0; j < m; j++) {
            temp_digits[j] = x % 3;
            x /= 3;
        }

        bool ok = true;
        for (int j = 0; j + 1 < m && ok; j++) {
            if (temp_digits[j] == 0 && temp_digits[j + 1] == 0)
                ok = false;
        }
        if (ok) {
            valid_states.push_back(mask);
            digits.push_back(temp_digits);
        }
    }

    int total_states = valid_states.size();
    transitions.assign(total_states, vector<int>());

    // Precompute valid transitions between states
    for (int i = 0; i < total_states; i++) {
        for (int j = 0; j < total_states; j++) {
            bool ok = true;
            for (int k = 0; k < m && ok; k++) {
                // No vertical adjacent empties
                if (digits[i][k] == 0 && digits[j][k] == 0)
                    ok = false;
                // State 2 must be above state 1
                if (digits[i][k] == 2 && digits[j][k] != 1)
                    ok = false;
            }
            if (ok) transitions[i].push_back(j);
        }
    }

    // Initialize DP
    for (int i = 0; i <= n; i++) {
        dp[i].assign(total_states, INF);
    }

    // Base case: first row
    for (int idx = 0; idx < total_states; idx++) {
        bool ok = true;
        int count = 0;
        for (int j = 0; j < m && ok; j++) {
            int s = digits[idx][j];
            if (s == 2) ok = false; // no bottom domino in first row
            if (s == 1) {
                if (grid[1][j] == '.') count++;
                else ok = false; // obstacle can't be covered
            } else if (s == 0 && grid[1][j] == '*') {
                ok = false;
            }
        }
        if (ok) dp[1][idx] = count;
    }

    vector<bool> is_horizontal(m);
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < total_states; j++) {
            bool ok = true;
            int cnt = 0;
            for (int k = 0; k < m && ok; k++) {
                int s = digits[j][k];
                if (s == 1 || s == 2) {
                    if (grid[i][k] == '.') {
                        cnt += (s == 1 ? 1 : 1);
                    } else {
                        ok = false;
                    }
                } else if (s == 0 && grid[i][k] == '*') {
                    ok = false;
                }
            }
            if (!ok) continue;

            for (int t_idx : transitions[j]) {
                if (dp[i - 1][t_idx] >= dp[i][j]) continue;

                ok = true;
                for (int k = 0; k < m && ok; k++) {
                    if (digits[j][k] == 2) {
                        if (digits[t_idx][k] != 1 || grid[i - 1][k] == '*')
                            ok = false;
                    }
                }
                if (!ok) continue;

                for (int k = 0; k < m; k++) {
                    is_horizontal[k] = (digits[t_idx][k] == 1 && grid[i - 1][k] == '.' && digits[j][k] != 2);
                }

                for (int k = 0; k < m && ok; k++) {
                    if (is_horizontal[k]) {
                        if (k + 1 < m && is_horizontal[k + 1]) {
                            is_horizontal[k] = is_horizontal[k + 1] = false;
                        } else {
                            ok = false;
                        }
                    }
                }

                if (ok) {
                    dp[i][j] = dp[i - 1][t_idx];
                }
            }
            dp[i][j] += cnt;
        }
    }

    int ans = INF;
    for (int idx = 0; idx < total_states; idx++) {
        bool ok = true;
        for (int j = 0; j < m; j++) {
            is_horizontal[j] = (digits[idx][j] == 1 && grid[n][j] == '.');
        }
        for (int j = 0; j < m && ok; j++) {
            if (is_horizontal[j]) {
                if (j + 1 < m && is_horizontal[j + 1]) {
                    is_horizontal[j] = is_horizontal[j + 1] = false;
                } else {
                    ok = false;
                }
            }
        }
        if (ok) ans = min(ans, dp[n][idx]);
    }

    cout << ans / 2 << '\n';
    return 0;
}