<|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.

527. Explode 'Em All
Time limit per test: 1.5 second(s)
Memory limit: 524288 kilobytes
input: standard
output: standard

The prime minister of Berland decided to build a new city in the country. It's hard to describe the excitement of all Berland citizens, but indeed this is great news from the economic, social and cultural standpoints.

The land in Berland is occupied almost entirely and it's very hard to find free space for construction, so it was decided to build the city on a stony terrain. The map of this terrain is represented as an nx m grid, where each cell of the grid is either an empty space or a rock.

Of course, before construction is started, the given terrain must be completely cleared from rocks. As you may guess, you were hired to complete this mission. Your goal is to destroy all rocks by dropping bombs from a plane. A bomb can be dropped on any cell of the map, and you are free to select where you want to drop each bomb. When a bomb targeted for cell (i, j) reaches the ground, it destroys all rocks in row i and also all rocks in column j of the grid. If cell (i, j) contains a rock, this rock is also destroyed.

Please help the prime minister of Berland to find the minimum number of bombs required to completely clear the given terrain from rocks.

Input
The first line of input contains two integers n and m (1 ≤ n,m ≤ 25) — the number of rows and columns correspondingly. Each of the next n lines contains m characters describing the terrain. An empty space is denoted by ".", while a rock is denoted by "*".

Output
Write a single integer to the output — the minimum numbers of bombs required for destroying all rocks on the terrain.

Example(s)
sample input
sample output
8 10
..........
..***..*.*
.*.......*
.*.......*
.*.......*
.....*****
..........
.........*
2

sample input
sample output
3 4
....
....
....
0



Note
In the first sample test it's only required to drop 2 bombs from a plane: one bomb to cell (2,2) and another bomb to cell (6, 10). Row and column indices in this explanation are 1-based.

<|response|>
1. Abridged problem statement
You have an n×m grid (1≤n,m≤25) with some cells containing rocks ('*') and others empty ('.'). Each bomb dropped at cell (i,j) destroys all rocks in row i and in column j. Find the minimum number of bombs needed to destroy every rock.

2. Key observations
- Dropping k bombs involves at most k distinct rows and k distinct columns (you can reuse rows or columns across bombs).
- Equivalently, we choose a set R of rows and a set C of columns so that every rock at (i,j) satisfies i∈R or j∈C. The number of bombs needed is max(|R|,|C|).
- For any fixed R, the smallest C is the set of all columns that still have rocks in rows not in R. So we only need to enumerate subsets R of rows, compute C automatically, and take cost=max(|R|,|C|).
- There are 2^n subsets R. With n≤25, 2^25≈33 million, which is borderline but feasible in optimized C++/Python with bit-operations.
- We represent each row by an m-bit bitmask of where its rocks are. We build an array mask[subset_of_rows] = bitwise OR of the masks of rows in that subset. Using the "lowbit" SOS-style DP trick, this table can be filled in O(2^n). Then for each R we look at mask[complement(R)] to see what columns remain needing coverage.

3. Full solution approach
Step 1. Read n, m and the grid.
Step 2. Build an array of single-row masks: for each row i, mask[1<<i] = bitmask of column positions with a rock in row i.
Step 3. Let N=1<<n. Fill mask for all subsets s from 1 to N-1 by:
    l = s & -s  (lowest set bit)
    mask[s] = mask[l] | mask[s ^ l]
Step 4. Let full = N-1. Initialize answer = n+m (an upper bound).
Step 5. For each subset i in [0..N-1] representing chosen rows R:
    rows_chosen = popcount(i)
    columns_needed = popcount(mask[full ^ i])
    cost = max(rows_chosen, columns_needed)
    answer = min(answer, cost)
Step 6. Print answer.
This runs in O(2^n) time and memory.

4. C++ implementation
```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;
};

int n, m;
vector<string> tbl;

void read() {
    cin >> n >> m;
    tbl.resize(n);
    cin >> tbl;
}

void solve() {
    // Each bomb clears one full row and one full column at once, so if a plan
    // bombs r distinct rows and c distinct columns we can pair them up and only
    // need max(r, c) bombs. We enumerate every subset i of the n rows that we
    // choose to bomb: those rows are cleared completely, and the rocks in the
    // remaining rows must be killed by bombing their columns. mask[s] holds the
    // union (bitmask over columns) of rock columns across the rows in set s,
    // built by SOS-style merging of single-row masks. For each chosen row set i
    // the needed columns are mask of the complement, and the cost is
    // max(popcount(rows), popcount(columns)); we minimise this over all subsets.

    vector<int> mask(1 << n, 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(tbl[i][j] == '*') {
                mask[1 << i] |= 1 << j;
            }
        }
    }

    for(int i = 1; i < (1 << n); i++) {
        int l = i & -i;
        mask[i] = mask[l] | mask[i ^ l];
    }

    int ans = n + m;
    for(int i = 0; i < (1 << n); i++) {
        int mask_m = mask[((1 << n) - 1) ^ i];
        ans = min(ans, max(__builtin_popcount(i), __builtin_popcount(mask_m)));
    }

    cout << ans << '\n';
}

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
```python
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    tbl = [input().strip() for _ in range(n)]

    # If there are no rocks, answer is 0.
    any_rock = any('*' in row for row in tbl)
    if not any_rock:
        print(0)
        return

    # To speed up, we enumerate on the smaller dimension (rows vs. columns).
    # If columns are fewer, we transpose the grid.
    transpose = False
    if m < n:
        transpose = True
        # Transpose tbl into size m x n
        new_tbl = [''.join(tbl[i][j] for i in range(n)) for j in range(m)]
        tbl = new_tbl
        n, m = m, n

    # Build single-row rock masks
    row_masks = []
    for i in range(n):
        mask = 0
        for j, ch in enumerate(tbl[i]):
            if ch == '*':
                mask |= 1 << j
        row_masks.append(mask)

    FULL = (1 << n) - 1
    # Precompute mask_union[s] = OR of row_masks over rows in subset s
    mask_union = [0] * (1 << n)
    # Initialize single-bit subsets
    for i in range(n):
        mask_union[1 << i] = row_masks[i]
    # Build up all subsets by lowbit trick
    for s in range(1, 1 << n):
        lowbit = s & -s
        if s != lowbit:
            mask_union[s] = mask_union[lowbit] | mask_union[s ^ lowbit]

    best = n + m
    # Enumerate all subsets of rows R (bitmask s)
    for s in range(1 << n):
        rows = s.bit_count()
        # Rocks not covered by these rows lie in rows in complement: FULL^s
        needed_cols = mask_union[FULL ^ s].bit_count()
        # cost = max(rows, needed_cols)
        cost = rows if rows >= needed_cols else needed_cols
        if cost < best:
            best = cost

    print(best)

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

Explanation summary: We reduce the bombing problem to covering all '*' positions by choosing some rows R and columns C so that each '*' is in R×anything or anything×C. The number of bombs needed is max(|R|,|C|). Enumerate all subsets of rows using bitmasks, compute the minimal needed columns for each choice via SOS-style DP, and take the minimum cost. This runs in O(2^n) time and memory.
