#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define cin std::cin
#define cout std::cout
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;

//const int MN = 2e5 + 20;
const int INF = 2e9 + 1000;//INF
const LL INFLL = 8e18 + 1000;//INF long long 
mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());
const int mod = 998244353;
//模板区域~~~~~~~

//模板结束~~~~~~~

void solve() {
    int n, m; cin >> n >> m;
    V<V<int>> a(n + 1, V<int>(m + 1));
    for(int i = 1; i <= n; i++) {
        string s; cin >> s;
        for(int j = 1; j <= m; j++) a[i][j] = s[j - 1] - '0';
    }
    if(n > m) {
        V<V<int>> b(m + 1, V<int>(n + 1));
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                b[i][j] = a[j][i];
            }
        }
        swap(n, m);
        swap(a, b);
    }
    
    V<V<int>> dp(n + 1, V<int>(n + 1, INF / 2));
    dp[1][n] = 0;

    auto cal_l = [&](int l, int r) -> int {
        int ll = l - (r - l + 1);
        ll = max(1, ll);
        return ll;
    };
    auto cal_r = [&](int l, int r, int n) -> int {
        int rr = r + (r - l + 1);
        rr = min(rr, n);
        return rr;
    };

    for(int len = n - 1; len >= 1; len--) {
        int mn = INF;
        for(int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;

            int ll = cal_l(l, r);
            int rr = cal_r(l, r, n);

            dp[l][r] = min(dp[l][r], dp[ll][r] + 1);
            dp[l][r] = min(dp[l][r], dp[l][rr] + 1);

            mn = min(dp[l][r], mn);
        }
        for(int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            if(dp[l][r] > mn + 1) assert(0);
        }
    }

    // for(int i = 1; i <= n; i++) {
    //     for(int j = 1; j <= n; j++) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    V<array<int, 3>> useful;

    for(int i = 1; i <= n; i++) {
        int now = 30;
        for(int j = i; j <= n; j++) {
            if(dp[i][j] < now) now = dp[i][j], useful.pb({i, j, dp[i][j]});
            // cout << i << " " << j << endl;
        }
    }
    
    // cout << useful.size() << endl;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) a[i][j] += a[i - 1][j];
    }

    V<int> v(m + 1);
    V<int> f(m + 1), n_f(m + 1);
    int totans = INF;
    for(auto [l, r, w] : useful) {
        for(int i = 1; i <= m; i++) v[i] = a[r][i] - a[l - 1][i] == r - l + 1;//, cout << a[r][i] - a[l - 1][i] << " ";

        bool ok = 0;

        for(auto &x : f) x = 0;

        for(int l = 1; l <= m; l++) {
            if(!v[l]) {
                f[l] = 0;
                continue;
            }
            int r = l;
            while(r <= m && v[r] == 1) r++;
            f[l] = r - 1;
            ok = 1;
            l = r - 1;
        }


        if(!ok) continue;
        int ans = w;

        // for(int i = 1; i <= n; i++) cout << v[i] << " ";
        // cout << endl;
        // for(int i = 1; i <= n; i++) cout << f[i] << " ";
        // cout << endl;

        while(1) {
            if(f[1] == m) break;
            for(auto &x : n_f) x = 0;
            for(int i = 1; i <= m; i++) {
                if(f[i] == 0) continue;
                int ll = cal_l(i, f[i]);
                int rr = cal_r(i, f[i], m);
                n_f[ll] = max(n_f[ll], f[i]);
                n_f[i] = max(n_f[i], rr);
            }
            ans++;
            swap(n_f, f);
        }
        // cout << l << " " << r << " " << w << endl;
        // cout << ans << endl;
        totans = min(ans, totans);
    }
    
    cout << totans << endl;
}

int32_t main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    // cin >> t;
    while (t--) 
    solve();
}