<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

132. Another Chocolate Maniac

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Bob really LOVES chocolate. He thinks he never gets enough. Imagine his joy when his parents told him that they would buy him many rectangular chocolate pieces for his birthday. A piece of chocolate is a 2x1 or 1x2 rectangle. Bob's parents also bought him a nice birthday cake, which can be imagined as a matrix having M rows and N columns. Some positions on the cake are occupied by candles, the others are empty. Bob's parents asked their son to place as many chocolate pieces as he can on the empty squares on the cake, in such a manner that no two chocolate pieces overlap. However, he would like to keep the chocolate pieces to himself. That's why, he wants to place only a minimal amount of them on the cake and keep the rest. In order not to make Mon and Dad suspicious, Bob wants to place the chocolate pieces in such a way, that no other piece may be placed on the cake (that is, there won't exist any two adjacent empty squares). Find the minimal number of pieces which need to be placed on the cake, so that they do not overlap and no extra piece may be added.


Input

The first line of the input contains 2 integers: M (1<=M<=70) and N (1<=N<=7). Next, M lines will follow, each of them containing N characters, describing the cake. The character on row i and column j of the cake may be either a '*' (ASCII code 42), representing a candle, or a '.' (ASCII code 46), representing an empty square.


Output

You should output one integer: the minimal amount of pieces of chocolate which need to be placed on the cake.


Sample Input

5 5
.*..*
*....
..**.
**.*.
.**..
Sample Output

4
Author  : Mugurel Ionut Andreica
Resource    : SSU::Online Contester Fall Contest #2
Date    : Fall 2002

<|response|>
1. Abridged Problem Statement  
Given an M×N grid (1≤M≤70, 1≤N≤7) of cells, some blocked (‘*’) and some empty (‘.’). We wish to place the fewest 1×2 or 2×1 dominoes on empty cells so that  
  • no two dominoes overlap, and  
  • after placement there is no pair of adjacent empty cells left (i.e. you cannot add another domino).  
Output the minimum number of dominoes needed.

2. Key Observations  
- We want a minimum-size *maximal* matching on the grid graph of empty cells (adjacent cells form edges).  
- Maximum bipartite‐matching plus greedy enlargement does not guarantee minimal maximal matching.  
- However, N≤7 is small. We can sweep the grid row by row in row-major order, maintaining a bitmask of size 2×N (up to 14 bits) that records which of the last two rows’ cells are already unavailable (either blocked by a candle or covered by a placed domino).  
- At each cell we update the mask by shifting it (dropping the oldest bit, bringing in a bit for the current cell), then consider three actions on an empty cell:  
  1) leave it free,  
  2) place a vertical domino with the cell above,  
  3) place a horizontal domino with the cell to the left.  
  For a blocked cell, we simply mark it unavailable.  
- To enforce maximality (no adjacent free pair can “escape” out of our 2-row window unseen), whenever we shift the window we check if the bit that was dropped and its neighbor (either to the right in the same row or below in the next row) were both free. If so, that branch is invalid.  
- At the end we inspect all masks that survive, and we only accept masks in which there is no remaining adjacent free pair in the final 2 rows. We take the minimum cost among those.

Time complexity: O(M·N·2^(2N)) ≈ 70·7·2^14 ≃ 8·10^6, which fits in 0.25 s.

3. Full Solution Approach  
1. Let W = 2·N. We index bits 0…W−1 in a mask. We keep a DP array dp[mask] = minimum dominoes used to reach this mask after processing some prefix of cells.  
2. We process cells in row-major order (i from 0 to M−1, j from 0 to N−1). For each cell:  
   a. We prepare next_dp[mask] = INF for all masks.  
   b. For each old mask with finite cost, we shift it left by 1: new_mask_base = (mask<<1) & ((1<<W)−1). This drops the bit at position W and makes room in bit 0 for the current cell.  
   c. If the cell is blocked (‘*’), we force-bit0=1: new_mask = new_mask_base | 1. We then check the “escape” condition (see below). If OK, update next_dp[new_mask] = min(next_dp[new_mask], old_cost).  
   d. If the cell is empty (‘.’), we try three cases:  
      i. leave it free (bit0=0): new_mask = new_mask_base.  
      ii. vertical domino with above cell: possible if i>0 and in the old mask the bit corresponding to the cell above was 0; we set that bit and bit0 to 1, cost+1.  
      iii. horizontal domino with left cell: possible if j>0 and in the old mask bit0 of the *old* mask was 0; we set bit0 and the bit that just shifted into bit1 to 1, cost+1.  
   e. After forming each candidate new_mask, run the escape check. If it passes, update next_dp.  
   f. Swap dp and next_dp.  
3. The *escape check* at position (i,j) on a shifted mask M′: if we have already processed ≥W cells, then a bit has just been dropped from position W in the 1-based shift. Let that dropped bit be d=(old_mask>>(W−1))&1. Its two potential neighbors when it was in the window were:  
   – horizontally: the bit at position W−1 (the cell to its right in the same row), valid only if j≠N−1 in the scan.  
   – vertically: the bit at position W−N (the cell below it).  
  If d==0 and either neighbor==0, then an uncovered adjacent pair escaped and we must reject this transition.  
4. After all cells, among dp[mask] still <INF, we scan each mask and verify no two adjacent free cells remain in those last two rows (check all horizontal and vertical pairs). We take the minimum cost.

4. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int INF = 1e9;

int m, n;
vector<vector<char>> cake;

void read() {
    cin >> m >> n;
    cin.ignore();
    cake = vector<vector<char>>(m, vector<char>(n));
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            cin >> cake[i][j];
        }
        cin.ignore();
    }
}

bool check_failure(int i, int j, int mask, int window_size) {
    if(i * n + j >= window_size) {
        if(!(mask & (1 << window_size)) && !(mask & (1 << (window_size - 1))) &&
           j != n - 1) {
            return true;
        }
        if(!(mask & (1 << window_size)) && !(mask & (1 << (window_size - n)))) {
            return true;
        }
    }

    return false;
}

void solve() {
    /*
     * Broken-profile DP over cells in row-major order. The DP mask holds the
     * occupancy of the last 2*n cells (a sliding window of two rows): bit 0 is
     * the cell just before the current one, going back up to the cell n rows
     * above. curr_dp[mask] = minimum chocolate pieces used to reach the current
     * cell with that window occupancy.
     *
     * At each cell we shift the window left by one and decide its state:
     *   - a candle ('*') is forced occupied;
     *   - an empty cell can be left empty, covered vertically by a piece with
     *     the cell directly above, or horizontally with the cell to its left.
     * check_failure rejects transitions that leave a cell finalized while it
     * and an already-fixed neighbour are both empty (an addable piece would
     * remain). After the sweep we keep masks whose trailing two rows admit no
     * further placeable piece and take the minimum count.
     */

    int window_size = 2 * n, full_mask = (1 << window_size) - 1;
    vector<int> curr_dp(1 << window_size, INF);
    vector<int> next_dp(1 << window_size, INF);

    curr_dp[0] = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            next_dp.assign(1 << window_size, INF);
            for(int mask = 0; mask < (1 << window_size); mask++) {
                if(curr_dp[mask] == INF) {
                    continue;
                }

                if(cake[i][j] == '*') {
                    int new_mask = mask << 1 | 1;
                    if(!check_failure(i, j, new_mask, window_size)) {
                        new_mask &= full_mask;
                        next_dp[new_mask] =
                            min(next_dp[new_mask], curr_dp[mask]);
                    }
                } else {
                    {
                        int new_mask = mask << 1;
                        if(!check_failure(i, j, new_mask, window_size)) {
                            new_mask &= full_mask;
                            next_dp[new_mask] =
                                min(next_dp[new_mask], curr_dp[mask]);
                        }
                    }

                    if(i > 0 && !(mask & (1 << (n - 1)))) {
                        int new_mask = (mask | (1 << (n - 1))) << 1 | 1;
                        if(!check_failure(i, j, new_mask, window_size)) {
                            new_mask &= full_mask;
                            next_dp[new_mask] =
                                min(next_dp[new_mask], curr_dp[mask] + 1);
                        }
                    }

                    if(j > 0 && !(mask & 1)) {
                        int new_mask = mask << 1 | 3;
                        if(!check_failure(i, j, new_mask, window_size)) {
                            new_mask &= full_mask;
                            next_dp[new_mask] =
                                min(next_dp[new_mask], curr_dp[mask] + 1);
                        }
                    }
                }
            }

            curr_dp = std::move(next_dp);
        }
    }

    int result = INF;
    for(int mask = 0; mask < (1 << window_size); mask++) {
        if(curr_dp[mask] == INF) {
            continue;
        }

        bool possible_tile = false;
        for(int i = 0; i < n; i++) {
            if(m != 1 && !(mask & (1 << i)) && !(mask & (1 << (i + n)))) {
                possible_tile = true;
                break;
            }

            if(i != n - 1 && !(mask & (1 << i)) && !(mask & (1 << (i + 1)))) {
                possible_tile = true;
                break;
            }

            if(i != n - 1 && m != 1 && !(mask & (1 << (i + n))) &&
               !(mask & (1 << (i + n + 1)))) {
                possible_tile = true;
                break;
            }
        }

        if(!possible_tile) {
            result = min(result, curr_dp[mask]);
        }
    }

    assert(result != INF);
    cout << result << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
def main():
    data = sys.stdin.read().split()
    M, N = map(int, data[:2])
    cake = data[2:]

    W = 2 * N
    FULL = (1 << W) - 1
    INF = 10**9

    # dp[mask] = minimal dominoes so far
    dp = [INF] * (1 << W)
    dp[0] = 0

    # Check if an uncovered adjacent pair escaped when shifting
    def escaped(i, j, old_mask):
        cells_done = i * N + j
        if cells_done < W:
            return False
        dropped = (old_mask >> (W-1)) & 1
        # horizontal neighbor (same row)
        if j != N-1:
            right_nb = (old_mask >> (W-2)) & 1
            if dropped==0 and right_nb==0:
                return True
        # vertical neighbor (row below)
        down_nb = (old_mask >> (W-1-N)) & 1
        if dropped==0 and down_nb==0:
            return True
        return False

    # Process cells
    for i in range(M):
        for j in range(N):
            next_dp = [INF] * (1 << W)
            for mask in range(1 << W):
                cost = dp[mask]
                if cost == INF:
                    continue
                base = ((mask << 1) & FULL)

                if cake[i][j] == '*':
                    # blocked cell
                    nm = base | 1
                    if not escaped(i, j, mask):
                        next_dp[nm] = min(next_dp[nm], cost)
                else:
                    # 1) leave free
                    nm = base
                    if not escaped(i, j, mask):
                        next_dp[nm] = min(next_dp[nm], cost)

                    # 2) vertical domino with above
                    if i > 0:
                        # above cell old bit was at index N-1
                        if ((mask >> (N-1)) & 1) == 0:
                            nm2 = base | 1
                            # after shift, the above cell maps to bit (N)
                            nm2 |= (1 << N)
                            if not escaped(i, j, mask):
                                next_dp[nm2] = min(next_dp[nm2], cost+1)

                    # 3) horizontal domino with left
                    if j > 0:
                        if (mask & 1) == 0:
                            nm3 = base | 3
                            if not escaped(i, j, mask):
                                next_dp[nm3] = min(next_dp[nm3], cost+1)

            dp = next_dp

    # Final check: no adjacent free cells remain
    ans = INF
    for mask in range(1 << W):
        cost = dp[mask]
        if cost == INF:
            continue
        bad = False
        for c in range(N):
            top    = (mask >> c) & 1
            bottom = (mask >> (c+N)) & 1
            if top==0 and bottom==0:
                bad = True; break
            if c+1 < N:
                if ((mask >> c)&1)==0 and ((mask>>(c+1))&1)==0:
                    bad = True; break
                if ((mask>>(c+N))&1)==0 and ((mask>>(c+N+1))&1)==0:
                    bad = True; break
        if not bad:
            ans = min(ans, cost)

    print(ans)

if __name__ == "__main__":
    main()
```

Explanation of major steps is in the comments. This rolling‐window DP over 2×N with escape checks enforces both correctness (no overlaps, no two adjacent free cells at any stage) and minimality of the number of dominoes.