#include <bits/stdc++.h>
#define MAX 805
using namespace std;
char mat[MAX][MAX];
int drum[MAX][MAX];
int N,S;
struct point
{
int l,c,niv;
};
queue<point>bear;
queue<point>bee;
int homeL,homeC;
void read()
{
cin>>N>>S;
int i,j;
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
{
cin>>mat[i][j];
if(mat[i][j]=='D')
{
homeL=i;
homeC=j;
}
}
}
int dl[]={-1,0,1,0};
int dc[]={0,1,0,-1};
bool continua;
void expand_bee()
{
int niv=(bee.empty())?0:bee.front().niv;
while(!bee.empty() && bee.front().niv==niv)
{
point curr=bee.front();
bee.pop();
int i;
for(i=0;i<4;++i)
{
int lnou=curr.l+dl[i];
int cnou=curr.c+dc[i];
if((mat[lnou][cnou]=='G' || mat[lnou][cnou]=='M') && drum[lnou][cnou]>=0)
{
drum[lnou][cnou]=niv-1;
bee.push({lnou,cnou,niv-1});
continua=1;
}
}
}
}
void expand_bear()
{
int niv=(bear.empty())?0:bear.front().niv;
while(!bear.empty() && bear.front().niv<niv+S)
{
point curr=bear.front();
bear.pop();
if(drum[curr.l][curr.c]<0)
continue;
int i;
for(i=0;i<4;++i)
{
int lnou=curr.l+dl[i];
int cnou=curr.c+dc[i];
if((mat[lnou][cnou]=='G' || mat[lnou][cnou]=='D') && !drum[lnou][cnou])
{
drum[lnou][cnou]=curr.niv+1;
bear.push({lnou,cnou,curr.niv+1});
continua=1;
}
}
}
}
bool check(int nr)
{
int i,j;
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
if(mat[i][j]=='M')
{
drum[i][j]=1;
bear.push({i,j,1});
}
else
if(mat[i][j]=='H')
{
drum[i][j]=-1;
bee.push({i,j,-1});
}
for(i=1;i<=nr;++i)
expand_bee();
continua=1;
while(continua)
{
continua=0;
expand_bear();
expand_bee();
}
int rasp=drum[homeL][homeC];
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
drum[i][j]=0;
while(!bee.empty())
bee.pop();
while(!bear.empty())
bear.pop();
return rasp>0;
}
int bin_search()
{
int left=-1;
int right=N*N;
while(right-left>1)
{
int mid=(left+right)/2;
if(check(mid))
left=mid;
else
right=mid;
}
return left;
}
void write()
{
cout<<bin_search();
}
int main()
{
read();
write();
return 0;
}
