#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <vector>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(auto i = (c).begin(); i != (c).end(); ++i)
#define BIT(n, m) (((n) >> (m)) & 1)

typedef long long ll;
typedef pair<int, int> PI;

const ll inf = 1e15;
const ll mod = 1000 * 1000 * 1000 + 7;
const double eps = 1e-9;

template <typename S, typename T> ostream &operator<<(ostream &out, const pair<S, T> &p) {
  out << "(" << p.first << ", " << p.second << ")";
  return out;
}

template <typename T> ostream &operator<<(ostream &out, const vector<T> &v) {
  out << "[";
  REP(i, v.size()){
    if (i > 0) out << ", ";
    out << v[i];
  }
  out << "]";
  return out;
}


int H, W, C, L;
vector<pair<int, int> > P;
map<pair<int, int>, vector<int> > M;
vector<vector<int> > B;
vector<tuple<int, int, int> > S;

void dfs(int pos, int sum, int &res){
  // cout << P[pos] <<" " << B << " " << pos << " " << sum << endl;
  if (pos == int(P.size())){
    // if (sum < res) cout << sum << endl;
    res = min(res, sum);
  } else if (sum + (C + L * L - 1) / (L * L) >= res){
    return;
  } else if (B[P[pos].first][P[pos].second] == 0){
    dfs(pos + 1, sum, res);      
  } else {
    vector<vector<int> > OLD_B = B;
    vector<pair<int, int> > order;
    for (int ind : M[P[pos]]){
      int score = 0;
      int h, w, d;
      tie(h, w, d) = S[ind];
      REP(i, d) REP(j, d) if (B[h + i][w + j] == 1) score++;
      order.push_back(make_pair(-score, ind));
    }
    sort(ALL(order));
    
    for (auto p : order){
      int ind = p.second;
      int h, w, d;
      tie(h, w, d) = S[ind];
      REP(i, d) REP(j, d) if (B[h + i][w + j] == 1){
        B[h + i][w + j] = 0;
        C--;
      }
      
      dfs(pos + 1, sum + 1, res);
      
      REP(i, d) REP(j, d) if (OLD_B[h + i][w + j] == 1){
        B[h + i][w + j] = OLD_B[h + i][w + j];
        C++;
      }
    }
  }
}

int main(){
  while (cin >> W >> H && W + H){
    vector<vector<int> > board(H, vector<int>(W));
    vector<tuple<int, int, int> > squares;

    REP(h, H) REP(w, W) cin >> board[h][w];
    REP(h, H) REP(w, W) REP2(d, 1, H + 1) if (h + d <= H && w + d <= W){
      bool ok = true;
      REP(i, d) REP(j, d) if (board[h + i][w + j] == 0) ok = false;
      if (ok) squares.push_back(make_tuple(h, w, d));
    }
    
    vector<int> use(squares.size(), true);
    REP(i, squares.size()) {
      REP(j, squares.size()) if (use[i] && use[j] && i != j){
        int h1, h2, w1, w2, d1, d2;
        tie(h1, w1, d1) = squares[j];
        tie(h2, w2, d2) = squares[i];
        if (h1 <= h2 && w1 <= w2 && h2 + d2 <= h1 + d1 && w2 + d2 <= w1 + d1){
          use[i] = false;
        }
      }
    }
    S.clear();
    P.clear();
    M.clear();
    B = board;
    C = 0;
    REP(i, squares.size()) if (use[i]) S.push_back(squares[i]);    

    REP(h, H) REP(w, W) if (board[h][w] == 1) {
      P.push_back(make_pair(h, w));
      C++;
    }
    REP(i, S.size()) REP(j, S.size()) if (j > 0){
      if (get<2>(S[j - 1]) < get<2>(S[j])) swap(S[j - 1], S[j]);
    }
    
    REP(i, S.size()){
      int h, w, d;
      tie(h, w, d)  = S[i];
      REP(j, d) REP(k, d) M[make_pair(h + j, w + k)].push_back(i);
    }
    int res = S.size();
    L = get<2>(S[0]);
    dfs(0, 0, res);
    cout << res << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1288