#include <stdio.h>
#include <queue>
using namespace std;
const int N=805;
char Base[N][N];
int Move[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
queue<int> q;
int dist[N][N];
void BFS(int s)
{
while(q.size())
{
int x=q.front()/N;
int y=q.front()%N;
q.pop();
for(int i=0;i<4;i++)
{
int nx=x+Move[i][0];
int ny=y+Move[i][1];
if(Base[nx][ny]=='G' && dist[nx][ny]==-1)
{
dist[nx][ny]=dist[x][y]+s;
q.push(nx*N+ny);
}
}
}
}
int tmp[N][N];
bool Check(int n, int s, int sx, int sy, int fx, int fy, int mid)
{
int i,j;
for(i=1;i<=n;i++) for(j=1;j<=n;j++) tmp[i][j]=-1;
if(dist[sx][sy]<=mid*s) return false;
tmp[sx][sy]=mid*s;
q.push(sx*N+sy);
while(q.size())
{
int x=q.front()/N;
int y=q.front()%N;
q.pop();
for(i=0;i<4;i++)
{
int nx=x+Move[i][0];
int ny=y+Move[i][1];
if((Base[nx][ny]=='G' && tmp[nx][ny]==-1 && dist[nx][ny]>tmp[x][y]+1) || (Base[nx][ny]=='D' && tmp[nx][ny]==-1))
{
tmp[nx][ny]=tmp[x][y]+1;
q.push(nx*N+ny);
}
}
}
return tmp[fx][fy]!=-1;
}
int main()
{
int n,s,i,j,sx,sy,fx,fy;
scanf("%i %i",&n,&s);
for(i=1;i<=n;i++) for(j=1;j<=n;j++) dist[i][j]=-1;
for(i=1;i<=n;i++)
{
scanf("%s",Base[i]+1);
for(j=1;j<=n;j++)
{
if(Base[i][j]=='M') sx=i,sy=j,Base[i][j]='G';
if(Base[i][j]=='D') fx=i,fy=j;
if(Base[i][j]=='H') q.push(i*N+j),dist[i][j]=0;
}
}
BFS(s);
int top=n*n,bot=0,mid,ans=-1;
while(top>=bot)
{
mid=top+bot>>1;
if(Check(n,s,sx,sy,fx,fy,mid)) ans=mid,bot=mid+1;
else top=mid-1;
}
printf("%i\n",ans);
return 0;
}
