#include <iostream>
using namespace std;
int n,s;
char map[1005][1005],tmap[1005][1005],tag[1005][1005];
int ex,ey,beetag[1005][1005],beartag[1005][1005],sx,sy,bee[1000005][3],bear[1000005][3];
int check(int step)
{
int beep=0,beepp=-1,bearp=0,bearpp=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
tag[i][j]=0;
beartag[i][j]=0;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(map[i][j]=='H')
{
beepp++;
bee[beepp][0]=i;
bee[beepp][1]=j;
bee[beepp][2]=0;
}
if(map[i][j]=='M')
{
bear[0][0]=i;
bear[0][1]=j;
bear[0][2]=0;
tag[i][j]=1;
map[i][j]='G';
}
}
}
while(beep<=beepp)
{
if(bee[beep][2]==step)break;
int nowx=bee[beep][0],nowy=bee[beep][1];
for(int i=1;i<=4;i++)
{
int tmpx=nowx,tmpy=nowy;
if(i==1)tmpx++;
if(i==2)tmpy++;
if(i==3)tmpx--;
if(i==4)tmpy--;
if((map[tmpx][tmpy]=='G' || map[tmpx][tmpy]=='M') && tmpx>0 && tmpy<=n && tmpy>0 && tmpy<=n)
{
beepp++;
bee[beepp][0]=tmpx;
bee[beepp][1]=tmpy;
bee[beepp][2]=bee[beep][2]+1;
map[tmpx][tmpy]='H';
}
}
beep++;
}
for(int i=1;i<=n;i++)
{
//for(int j=1;j<=n;j++)cout<<map[i][j];
//cout<<endl;
}
int count=n*n,bearstep=0;
while(count--)
{
bearstep+=s;
while(bearp<=bearpp)
{
//cout<<bear[bearp][0]<<" "<<bear[bearp][1]<<" "<<bear[bearp][2]<<endl;
if(bear[bearp][2]==bearstep)break;
int nowx=bear[bearp][0],nowy=bear[bearp][1];
if(map[nowx][nowy]=='H')
{
bearp++;
continue;
}
for(int i=1;i<=4;i++)
{
int tmpx=nowx,tmpy=nowy;
if(i==1)tmpx++;
if(i==2)tmpy++;
if(i==3)tmpx--;
if(i==4)tmpy--;
if(map[tmpx][tmpy]=='D')return 1;
if(map[tmpx][tmpy]=='G' && tmpx>0 && tmpy<=n && tmpy>0 && tmpy<=n && tag[tmpx][tmpy]==0)
{
bearpp++;
bear[bearpp][0]=tmpx;
bear[bearpp][1]=tmpy;
bear[bearpp][2]=bear[bearp][2]+1;
tag[tmpx][tmpy]=1;
}
}
bearp++;
}
step++;
//cout<<step<<" "<<count<<endl;
while(beep<=beepp)
{
//cout<<bee[beep][0]<<" "<<bee[beep][1]<<" "<<bee[beep][2]<<endl;
if(bee[beep][2]==step)break;
int nowx=bee[beep][0],nowy=bee[beep][1];
for(int i=1;i<=4;i++)
{
int tmpx=nowx,tmpy=nowy;
if(i==1)tmpx++;
if(i==2)tmpy++;
if(i==3)tmpx--;
if(i==4)tmpy--;
if(map[tmpx][tmpy]=='G' && tmpx>0 && tmpy<=n && tmpy>0 && tmpy<=n)
{
beepp++;
bee[beepp][0]=tmpx;
bee[beepp][1]=tmpy;
bee[beepp][2]=bee[beep][2]+1;
map[tmpx][tmpy]='H';
}
}
beep++;
}
//cout<<endl;
}
return 0;
}
int main()
{
cin>>n>>s;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>map[i][j];
tmap[i][j]=map[i][j];
}
}
int l=0,r=n*n,ans=-1;
while(l<=r)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
map[i][j]=tmap[i][j];
}
}
int mid=(l+r)/2;
if(check(mid)==1)
{
ans=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<ans;
}
