#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> a(n);
for (auto &i : a)
cin >> i;
vector<vector<int>> u(n, vector<int>(m)), d = u;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
u[i][j] = (a[i][j] == '0' ? 0 : (i ? u[i - 1][j] + 1 : 1));
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++)
d[i][j] = (a[i][j] == '0' ? 0 : (i + 1 != n ? d[i + 1][j] + 1 : 1));
}
vector<int> ans(m, INT_MAX);
for (int i = 0; i < n; i++) {
int l = -1, mn1 = INT_MAX, mn2 = mn1;
for (int j = 0; j < n; j++) {
if (a[i][j] == '0') {
l = -1;
mn1 = mn2 = INT_MAX;
continue;
}
if (!~l) l = j;
mn1 = min(mn1, u[i][j]);
mn2 = min(mn2, d[i][j]);
ans[j - l] = min(ans[j - l], mn1 + mn2 - 1);
}
}
for (int i = m - 1; i >= 0; i--)
if (ans[i] != INT_MAX) return cout << ans[i], 0;
}
