#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
#pragma GCC optimize("Ofast,unroll-loops")
int n, m, maxMask;
vector<string> a;
int dp_prev[1<<10], dp_cur[1<<10];
vector<int> submasks[1<<10];
int hcost[1<<10];
inline int popc(int x) { return __builtin_popcount(x); }
int run(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
a.resize(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
maxMask = (1<<m) - 1;
// Tiền xử lý tất cả submasks
for(int mask = 0; mask <= maxMask; mask++){
submasks[mask].clear();
int s = mask;
do {
submasks[mask].push_back(s);
if(s == 0) break;
s = (s-1) & mask;
} while(true);
}
// Khởi dp_prev
for(int mask = 0; mask <= maxMask; mask++) dp_prev[mask] = INF;
dp_prev[0] = 0;
// DP theo hàng
for(int row = 0; row < n; row++){
// tính row_mask
int row_mask = 0;
for(int j = 0; j < m; j++){
if(a[row][j] == '#') row_mask |= (1<<j);
}
// tính hcost[u] cho u từ 0..maxMask
// hcost[u] = số đoạn ngang khi đã che các cột thuộc u, cần che những bit của row_mask & ~u
for(int u = 0; u <= maxMask; u++){
int seg = 0;
bool in_seg = false;
int need_mask = row_mask & ~u;
for(int j = 0; j < m; j++){
if(need_mask & (1<<j)){
if(!in_seg){
seg++;
in_seg = true;
}
} else {
in_seg = false;
}
}
hcost[u] = seg;
}
// reset dp_cur
for(int mask = 0; mask <= maxMask; mask++){
dp_cur[mask] = INF;
}
// chuyển dp
for(int mask_in = 0; mask_in <= maxMask; mask_in++){
int base = dp_prev[mask_in];
if(base >= INF) continue;
// mask_in phải là con mask của row_mask (không kéo xuống ở ô '.')
if(mask_in & ~row_mask) continue;
// cho mọi mask_out con của row_mask
// submasks[row_mask] đã tiền tính
for(int mask_out : submasks[row_mask]){
// tính cost
// mới dán dọc: bits in mask_out but not in mask_in
int vert_new = popc(mask_out & ~mask_in);
// union để lấy hcost
int u = mask_in | mask_out;
int cost = base + vert_new + hcost[u];
// cập nhật
if(cost < dp_cur[mask_out]){
dp_cur[mask_out] = cost;
}
}
}
// chuyển đổi
memcpy(dp_prev, dp_cur, sizeof dp_cur);
}
// kết quả
int ans = INF;
for(int mask = 0; mask <= maxMask; mask++){
ans = min(ans, dp_prev[mask]);
}
cout << ans << "\n";
return 0;
}
int main(){
return run();
}
