#include <bits/stdc++.h>

using namespace std;

int h, w, a[1000000], b[1000000], c[1000000];
int ans = 1e9;

int calc(int a, int b, int c) {
//  cout << a << ' ' << b << ' ' << c << '\n';
  int l = a, w = b - a, r = c - b;
  if (l > r) swap(l, r);
  int t = 32 - __builtin_clz((r + w - 1) / w << 1 | 1);
  a = (l + w - 1) / w;
//  cout << t << '\n';
  if (!a) return t - 1;
  int k = 31 - __builtin_clz(a);
//  cout << k << '\n';
//  cout << (1 << k + 1) * w + -l % w << ' ' << '\n';
  if ((1 << k + 1) * w + -l % w >= 0 && t >= k + 2 && ((1 << k + 1) * w + -l % w) * ((1 << t - k - 2) - 1) + w * ((1 << k + 1) - a - 1) >= r) return
//  cout << t - 1 << '\n',
  t - 1;
  return t;
}

void dc(int l, int r, int L, int R) {
  if (r <= l || R <= L) return;
  if (R - L <= r - l) {
    int m = (r + l) / 2;
    for (int j = L; j < R; ++j) {
      b[j] = c[j] = 0;
      while (m - b[j] >= l && a[(m - b[j]) * w + j]) ++b[j];
      while (m + c[j] < r && a[(m + c[j]) * w + j]) ++c[j];
      int mib = 1e9, mic = 1e9;
      for (int k = j; k >= L; k--) {
        mib = min(mib, b[k]);
        mic = min(mic, c[k]);
        if (mib) ans = min(ans, calc(k, j + 1, w) + calc(m - mib + 1, m + mic, h));
      }
    }
    dc(l, m, L, R);
    dc(m + 1, r, L, R);
  } else {
    int M = (R + L) / 2;
    for (int i = l; i < r; ++i) {
      b[i] = c[i] = 0;
      while (M - b[i] >= L && a[i * w + M - b[i]]) ++b[i];
      while (M + c[i] < R && a[i * w + M + c[i]]) ++c[i];
      int mib = 1e9, mic = 1e9;
      for (int k = i; k >= l; k--) {
        mib = min(mib, b[k]);
        mic = min(mic, c[k]);
        if (mib) ans = min(ans, calc(k, i + 1, h) + calc(M - mib + 1, M + mic, w));
      }
    }
    dc(l, r, L, M);
    dc(l, r, M + 1, R);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> h >> w;
  for (int i = 0; i < h; ++i) if (string s; cin >> s)
  for (int j = 0; j < w; ++j) a[i * w + j] = s[j] - '0';
  dc(0, h, 0, w);
  cout << ans;
}