#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define Lg(x) 31 - __builtin_clz(x)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 1e3 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void setupIO(){
#define name "Whisper"
//Phu Trong from Nguyen Tat Thanh High School for gifted student
srand(time(NULL));
cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
cout << fixed << setprecision(10);
}
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
int nCol, nRow;
char a[MAX][MAX];
void Whisper(){
cin >> nRow >> nCol;
REP(i, nRow) REP(j, nCol) cin >> a[i][j];
vector<int> F(MASK(nCol)), G(MASK(nCol), INF);
G[0] = 0;
REP(i, nRow) REP(j, nCol){
for (int msk = 0; msk < MASK(nCol); ++msk){
if (a[i][j] == '.'){
if (BIT(msk, j)) F[msk] = INF;
else F[msk] = min(G[msk], G[msk ^ MASK(j)]);
}
else{
if (BIT(msk, j)){
F[msk] = min(G[msk], G[msk ^ MASK(j)] + 1);
}
else{
F[msk] = min(G[msk], G[msk ^ MASK(j)]);
if (j == 0 || a[i][j - 1] == '.' || BIT(msk, j - 1)) F[msk]++;
}
}
}
swap(F, G);
}
int ans = INF;
for (int msk = 0; msk < MASK(nCol); ++msk){
minimize(ans, G[msk]);
}
cout << ans;
/*
using dp[i][j][msk] as the minimum that the state i and j is the current row and column
and the mask that represents what happened on the last m square, the current square, squares
that are in the current row and on the left side, and square is in the previous row that are
on the right side of the current square
bit 0 mean that the row j is covered by a horizontal piece of tape
bit 1 mean that the row j is covered by a vertical piece of tape
1. a[i][j] = '.'
dp[i][j][msk] = min(dp[i][j - 1][msk], dp[i][j - 1][msk ^ MASK(j) + 1]
2. a[i][j] != '.'
if (the j - th bit is 1)
dp[i][j][msk] = min(dp[i][j - 1][msk]) // the previous square has the same state with current
dp[i][j][msk] = min(dp[i][j - 1][msk ^ MASK(j)] + 1) // (the previous square is covered by a horizontal piece of tape
so we make a new vertical piece of tap -> + 1)
if (the j - th bit is 0)
dp[i][j][msk] = min(dp[i][j][msk, dp[i][j][msk ^ MASK(j)] (update for new state)
if (i == 0 || s[i][j - 1] == '.' || BIT(msk, j - 1)) dp[i][j][msk]++ (make a new horizontal piece of tape)
3. we can also optimize the memory by using two array F and G
F(msk) : the minimum tape we need to cover all the close till i row and j column
G(msk) : the minimum tape we need to cover all the colose till i row and j - 1 column
*/
}
signed main(){
setupIO();
int Test = 1;
// cin >> Test;
for ( int i = 1 ; i <= Test ; i++ ){
Whisper();
if (i < Test) cout << '\n';
}
}
