#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
char s[1009];
int mat[1009][1009];
int f[1000009];
int br[1000009],bc[1000009];
int vr[1009],vc[1009];
vector<int> sr[1009],sc[1009],sf[1000009];
int fnd(int x)
{
	return x==f[x]?x:f[x]=fnd(f[x]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			mat[i][j]=s[j]=='.'?0:1;
	}
	mat[1][1]=mat[1][m]=mat[n][1]=mat[n][m]=1;
	// for(int i=1;i<=n;i++)
	// 	for(int j=1;j<=m;j++)
	// 		printf("%d%c",mat[i][j],j==m?'\n':' ');
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int num=(i-1)*m+j;
			br[num]=i;
			bc[num]=j;
			if(mat[i][j])
			{
				sr[i].push_back(num);
				sc[j].push_back(num);
			}
		}
	for(int i=1;i<=n*m;i++)
		f[i]=i;
	for(int i=1;i<=n;i++)
	{
		int lst=0;
		for(int u:sr[i])
		{
			// printf("i:%d u:%d\n",i,u);
			if(lst)
				f[fnd(u)]=fnd(lst);
			else
				lst=u;
		}
	}
	for(int i=1;i<=m;i++)
	{
		int lst=0;
		for(int u:sc[i])
			if(lst)
				f[fnd(u)]=fnd(lst);
			else
				lst=u;
	}
	// for(int i=1;i<=n*m;i++)
	// 	printf("i:%d fnd:%d\n",i,fnd(i));
	for(int i=1;i<=n*m;i++)
		sf[fnd(i)].push_back(i);
	int ansr=-1,ansc=-1;
	for(int i=1;i<=n*m;i++)
	{
		if(sf[i].size()>1)
		{
			int tr=0,tc=0;
			for(int u:sf[i])
			{
				// printf("i:%d u:%d\n",i,u);
				if(!vr[br[u]])
					vr[br[u]]=1,tr++;
				if(!vc[bc[u]])
					vc[bc[u]]=1,tc++;
			}
			ansr++,ansc++;
		}
	}
	for(int i=1;i<=n;i++)
		if(!vr[i])
			ansr++;
	for(int i=1;i<=m;i++)
		if(!vc[i])
			ansc++;
	printf("%d",min(ansr,ansc));
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Vll =vector<ll>;
using VVll =vector<vector<ll>>;
template <class T>
using Vec = vector<T>;
template <class T>
using VVec = vector<vector<T>>;

void Z(){ cout<<"Test"<<endl; }

template <class T> void VVcout(VVec<T> A){ for(auto Vi:A) { for(auto i:Vi)cout<<i<<' '; cout<<endl;}}



VVll make_binary_VVll(VVll A,ll p){
    VVll Ab=A;
    ll ni=A.size();
    ll nj=A.at(0).size();


    for(ll i=0;i<ni;i++) for(ll j=0;j<nj;j++){
        ll a=A.at(i).at(j);
        if(a<=p) a=1;
        else a=0;
        Ab.at(i).at(j)=a;
    }

    return Ab;

}

VVll addsum(VVll A){
    VVll Ab=A;
    ll ni=A.size();
    ll nj=A.at(0).size();
    for(ll i=0;i<ni;i++) for(ll j=0;j<nj;j++){
        ll a=A.at(i).at(j);
        ll upper_sum=0,left_sum=0,upper_left_sum=0;
        if(i!=0) upper_sum+=Ab.at(i-1).at(j);
        if(j!=0) left_sum+=Ab.at(i).at(j-1);
        if(i!=0 && j!=0)  upper_left_sum+=Ab.at(i-1).at(j-1);

        Ab.at(i).at(j)=left_sum+upper_sum-upper_left_sum+a ;
    }

    return Ab;





}


bool check_p(VVll addsum_A,ll k,ll n,ll ci){

    ll addsum;

    bool ans=false;

    for(ll i=0;i<n-k+1;i++) for(ll j=0;j<n-k+1;j++){
        ll sum=0,upper_sum=0,left_sum=0,upper_left_sum=0;
        sum=addsum_A.at(i+k-1).at(j+k-1);
        if(i!=0) upper_sum+=addsum_A.at(i-1).at(j+k-1);
        if(j!=0) left_sum+=addsum_A.at(i+k-1).at(j-1);
        if(i!=0 && j!=0)  upper_left_sum+=addsum_A.at(i-1).at(j-1);

        addsum=sum+-left_sum-upper_sum+upper_left_sum ;

        if(addsum>=ci) ans=true;

    }

    return ans;



}













int main(){
    ll n,k,a;
    cin>>n>>k;

    VVll A(n,Vll(n));
    
    for(ll i=0;i<n;i++) for(ll j=0;j<n;j++){
        cin>>a;
        A.at(i).at(j)=a;
    }


    ll min=-1;

    ll centeri;

    if(k%2==0) centeri=(k*k)/2;

    else centeri=(k*k+1)/2;

    ll l=-1,r=1000000000LL+1;


    while(r-l>1){
        ll m=(l+r)/2;

        VVll binA,addsumA;

        binA=make_binary_VVll(A,m);

        addsumA=addsum(binA);

        //VVcout(binA);
        //VVcout(addsumA);

        //cout<<l<<' '<<m<<' '<<r<<endl;


        
        if(check_p(addsumA,k,n,centeri))  r=m;
        else l=m;

        
        
        //cout<<endl;
    }







    
    

    cout<<r<<endl;

}
