#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
#define MAX_W 10
#define INF 1E9

using namespace std;
typedef unsigned long long ull;

const ull B = 100000007;
int w, h; 
int s[MAX_W][MAX_W]; //可延伸的最大正方形邊長
int contain[MAX_W][MAX_W];
bool same[MAX_W][MAX_W][MAX_W][MAX_W];
int limit;
int ct;
unordered_map<ull, int> mp;

struct P{
	int x, y, size;
	P() {}
	P(int x, int y, int size) : x(x), y(y), size(size) {}
	bool operator < (const P& other) const{
		return size < other.size;
	}
};
void show(vector<int>& cover){
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			printf("%d ", (cover[i] >> (w - 1 - j)) & 1);
		}
		cout << endl;
	}
	cout << endl;
}
void init(vector<int>& f){
	memset(contain, 0, sizeof(contain));
	memset(same, false, sizeof(same));
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			s[i][j] = (f[i] >> (w - 1 - j)) & 1;
		}
	}
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			for(int k = 0;; k++){
				bool ok = true;
				if(i + k < h && j + k < w){
					for(int l = 0; ok && l <= k; l++){
						if(s[i + k][j + l] == 0 || s[i + l][j + k] == 0) ok = false;
					}
				}else{
					ok = false;
				}
				if(!ok){
					s[i][j] = k;
					break;
				}
			}
			for(int a = 0; a < s[i][j]; a++){
				for(int b = 0; b < s[i][j]; b++){
					contain[i + a][j + b]++;
				}
			}
			for(int a = 0; a < s[i][j] * s[i][j]; a++){
				int x1 = i + a / s[i][j], y1 = j + a % s[i][j];
				for(int b = 0; b < s[i][j] * s[i][j]; b++){
					int x2 = i + b / s[i][j], y2 = j + b % s[i][j];
					same[x1][y1][x2][y2] = same[x2][y2][x1][y1] = true;
				}
			}
		}
	}
}
ull calc_hash(vector<int>& f){
	ull t = 0;
	for(int i = 0; i < f.size(); i++){
		t = t * B + f[i];
	}
	return t;
}
int greedy(vector<int> f){
	int res = 0;
	bool update;
	do{
		update = false;
		int m_i, m_j, max = 0;
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				if(s[i][j] > 0){
					int tmp = 0, m = ((1 << s[i][j]) - 1) <<  (w - j - s[i][j]);
					for(int k = 0; k < s[i][j]; k++){
						tmp += __builtin_popcount(f[i + k] & m);
					}
					if(max < tmp){
						max = tmp;
						m_i = i, m_j = j;
					}
				}
			}
		}
		if(max > 0){
			int m = ((1 << s[m_i][m_j]) - 1) << (w - m_j - s[m_i][m_j]);
			for(int i = 0; i < s[m_i][m_j]; i++) f[m_i + i] &= ~m;
			res++;
			update = true;
		}
	}while(update);
	return res;
}
int hstar(vector<int> f){
	//選取盡量多的點，其中每個集合最多只能有一個點被選中
	vector<P> ps, X;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if((f[i] >> (w - 1 - j)) & 1){
				ps.push_back(P(i, j, contain[i][j]));
			}
		}
	}
	sort(ps.begin(), ps.end());
	for(int i = 0; i < ps.size(); i++){
		bool ok = true;
		int x1 = ps[i].x, y1 = ps[i].y;
		for(int j = 0; j < X.size() && ok; j++){
			int x2 = X[j].x, y2 = X[j].y;
			if(same[x1][y1][x2][y2]) ok = false;
		}
		if(ok) X.push_back(ps[i]);
	}
	return X.size();
}
int dfs(int num, vector<int> f, int idx){
	if(num + hstar(f) > limit) return INF;
	
	// printf("num = %2d  hstar = %2d   greedy = %2d\n", num,  hstar(f), greedy(f));
	// ull t = calc_hash(f);
	// if(mp.find(t) != mp.end() && mp[t] <= num) return INF;
	// mp[t] = num;
	ct++;
	// if(ct % 10000 == 0) cout << ct << endl;
	
	vector<int> reset(f.begin(), f.end());
	for(; idx < w * h; idx++){
		int i = idx / w, j = idx % w;
		int k = s[i][j];
		if(k > 0){
			int tmp = ((1 << k) - 1) << (w - j - k), n = 0;
			for(int m = 0; m < k; m++){
				if((f[i + m] & (~tmp)) == f[i + m]) n++;
				f[i + m] &= ~tmp;
			}
			if(n < k){
				if(dfs(num + 1, f, idx + 1) < INF) return num;
			}
			//f.assign(reset.begin(), reset.end());
			for(int m = 0; m < k; m++) f[i + m] = reset[i + m];
			if(((f[i] >> (w - 1 - j)) & 1) && n < k) break;
		}
	}	
	bool check = true;
	for(int i = 0; i < h && check; i++) check &= (f[i] == 0);
	return (check ? num : INF);
}
int solve(vector<int>& f){
	init(f);
	ct = 0;
	for(limit = greedy(f);; limit--){
		// printf("limit = %d\n", limit);
		mp.clear();
		if(dfs(0, f, 0) == INF) return limit + 1;
	}
}
int main(){
	while(cin >> w >> h && (w || h)){
		vector<int> f(h, 0);
		for(int i = 0; i < h; i++){
			f[i] = 0;
			int a;
			for(int j = 0; j < w; j++){
				cin >> a;
				f[i] = (f[i] << 1) | a;
			}
		}
		cout << solve(f) << endl;
		// cout << "ct = " << ct << "\n\n";
	}
	return 0;
}


Measured memory_bytes: 3084