#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n,m,stx,sty,edx,edy,bee[805][805],st,md,ed,d[805][805],bear[805][805];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1},u,v,x,y;
char s[805][805];
queue<pair<int,int> > q;
void debug(int kk)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(bee[i][j]==1e9)
{
printf("-1 ");
continue;
}
printf("%d ",bee[i][j]);
}
printf("\n");
}
printf("\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(bear[i][j]==1e9)
{
printf("-1 ");
continue;
}
printf("%d ",bear[i][j]/m+kk);
}
printf("\n");
}
printf("\n");
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)bee[i][j]=1e9,bear[i][j]=1e9;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i][j]=='M')
{
stx=i,sty=j;
}else if(s[i][j]=='D')
{
edx=i,edy=j;
}else if(s[i][j]=='H')
{
q.push({i,j});
bee[i][j]=0;
}
}
}
while(!q.empty())
{
u=q.front().X,v=q.front().Y;
q.pop();
for(int i=0;i<4;i++)
{
x=u+dx[i],y=v+dy[i];
if(x>=1&&x<=n&&y>=1&&y<=n)
{
if((s[x][y]=='G'||s[x][y]=='M')&&bee[x][y]==1e9)
{
bee[x][y]=bee[u][v]+1;
q.push({x,y});
}
}
}
}
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(bee[i][j]==1e9)
{
printf("-1 ");
continue;
}
printf("%d ",bee[i][j]);
}
printf("\n");
}
printf("\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(bear[i][j]==1e9)
{
printf("-1 ");
continue;
}
printf("%d ",bear[i][j]);
}
printf("\n");
}
printf("\n");
*/
st=0;
ed=1e9;
while(ed>=st)
{
md=(st+ed)/2;
//printf("%d %d %d\n",st,md,ed);
memset(d,-1,sizeof d);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)bear[i][j]=1e9;
d[stx][sty]=0;
bear[stx][sty]=0;
q.push({stx,sty});
while(!q.empty())
{
u=q.front().X,v=q.front().Y;
q.pop();
for(int i=0;i<4;i++)
{
x=u+dx[i],y=v+dy[i];
if(x>=1&&x<=n&&y>=1&&y<=n)
{
if((s[x][y]=='G'||s[x][y]=='M'||s[x][y]=='D')&&d[x][y]==-1)
{
if((bear[u][v]+1)/m+md<bee[x][y])
{
d[x][y]=0;
bear[x][y]=bear[u][v]+1;
q.push({x,y});
}
}
}
}
}
//debug(md);
if(d[edx][edy]==0&&md<bee[stx][sty])
{
st=md+1;
}else
{
ed=md-1;
}
}
//printf("%d %d %d\n",st,md,ed);
printf("%d\n",ed);
}
