#include<bits/stdc++.h>
#define int long long
using namespace std;
int wys[1000100];
int lewo[1000100];
int prawo[1000100];
int policz(int pocz,int kon,int a,int b)
{
    if(a>b)
        return 0;
    int x=a-pocz;
    int y=kon-b;
    //cout<<a<<" "<<b<<"\n";
    int dl=b-a+1;
    //cout<<"poczatek: "<<x<<" "<<y<<" "<<dl<<"\n";
    //return 0;
    int wynik=0;
    while(x>0 || y>0)
    {
        //cout<<x<<" "<<y<<" "<<dl<<"\n";
        if(x>y)
            swap(x,y);
        int pomoc=(x+dl-1);
        pomoc/=dl;
        if(pomoc%2==1)
        {
            int pop_x=x;
            x=max((int)0,x-dl);
            dl+=min(pop_x,dl);
        }
        else{
            int pop_y=y;
            y=max((int)0,y-dl);
            dl+=min(pop_y,dl);
        }
        wynik++;
    }
    //cout<<wynik<<"\n";
    return wynik;
}
int32_t main()
{
    //cin.tie(0);
    //cout.tie(0);
    //ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    int wynik=1e9;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        s="#"+s;
        for(int j=1;j<=m;j++)
        {
            if(s[j]=='0')
                wys[j]=0;
            else wys[j]++;
            //cout<<wys[j]<<" ";
        }
        //cout<<"\n";
        vector<int> stos;
        stos.push_back(0);
        for(int j=1;j<=m;j++)
        {
            while(stos.back()!=0 && wys[stos.back()]>=wys[j])
                stos.pop_back();
            lewo[j]=stos.back();
            stos.push_back(j);
        }
        stos.clear();
        stos.push_back(m+1);
        for(int j=m;j>=1;j--)
        {
            while(stos.back()!=m+1 && wys[stos.back()]>=wys[j])
                stos.pop_back();
            prawo[j]=stos.back();
            stos.push_back(j);
        }
        for(int j=1;j<=m;j++)
        {
            if(wys[j]!=0)
            wynik=min(wynik,policz(1,n,i-wys[j]+1,i)+policz(1,m,lewo[j]+1,prawo[j]-1));
            //cout<<"\n";
        }
    }
    cout<<wynik;
    return 0;
}