#include<iostream>
#include<cassert>
#include<climits>
#include<map>
#include<vector>
#include<utility>
#include<tuple>
using namespace std;

const int MAX_HEIGHT = 100, MAX_WIDTH = 10;

constexpr int fib(int n) {
	int a = 0, b = 1, tmp = 0;
	while (n--) {
		// `tie`/`make_pair` does not evaluate as constexpr in Kattis' Problemtools (probably outdated C++ standard)
		// tie(a, b) = make_pair(b, a + b);
		tmp = a + b;
		a = b;
		b = tmp;
	}
	return a;
}

const int CAN_PLACEMENTS = fib(MAX_WIDTH + 1);
int n, m, F[MAX_HEIGHT+2], a[MAX_HEIGHT] = {};

int pc[CAN_PLACEMENTS]; // number of cans used
int cover[CAN_PLACEMENTS]; // covering pattern
map<int,int> lookup;
vector<int> supports[CAN_PLACEMENTS];

int recurse(int row, int lstcan) {
	if (row == n/2) return 0; // we are done

	int result = INT_MAX/2;
	for (int curcan : supports[lstcan]) {
		if (a[row] & ~cover[curcan]) continue;
		result = min(result, pc[curcan] + recurse(row+1, curcan));
	}
	return result;
}

int main() {
	cin >> n >> m;
	for (int i = n-1; i >= 0; i--) {
		string S;
		cin >> S;
		for (int j = 0; j < m; j++)
			if (S[j] == '#')
				a[i/2] |= (1<<j);
	}
 
	for (int i=0; i <= m+1; i++) F[i] = fib(i);

	cover[0] = pc[0] = 0; // empty pattern: if you use this somewhere, it's going to stay empty
	supports[0].push_back(0);
	for (int i = 2; i <= m; i++) {
		for (int j = 0; j < F[i-1]; j++) {
			cover[F[i] + j] = cover[j] | (3<<(i-2));
			pc[F[i] + j] = pc[j] + 1;
		}
	}

	int num_placements = F[m+1];
	for (int i=0; i < num_placements; i++)
		lookup[cover[i]] = i;

	for (int i = 2; i <= m; i++) {
		for (int j = 0, k = F[i]; j < F[i-1]; j++, k++) {
			for (int sup : supports[j]) {
				int msk = cover[sup];

				// nothing added:
				supports[k].push_back(sup);

				// something added to the left:
				if (i > 2 && (msk & (3<<(i-3))) == 0)
					supports[k].push_back(lookup[ msk | (3<<(i-3)) ]);
				// something added above:
				if (         (msk & (3<<(i-2))) == 0)
					supports[k].push_back(lookup[ msk | (3<<(i-2)) ]);
				// something added to the right:
				if (i < m && (msk & (3<<(i-1))) == 0)
					supports[k].push_back(lookup[ msk | (3<<(i-1)) ]);
				// something added to the left and right:
				if (2 < i && i < m && (msk & (15<<(i-3))) == 0)
					supports[k].push_back(lookup[ msk | (15<<(i-3)) ]);
			}
		}
	}

	int allcans = 0;
	for (int i=0; i < num_placements; i++)
		if (pc[i] == m/2) allcans = i;
	assert(allcans != 0);
	cout << recurse(0, allcans) << endl;
}