#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define lim 1000001
using namespace std;
int mod=1000000007ll;
int n,s;
string g[802];
#define pii pair<int,int>
#define ppp pair<pii,pii>
pii bear;
vector<pii>hives;
bool check(int m){
set<ppp>q;
q.insert({{m*s,0},bear});
bool infected[n+2][n+2];
memset(infected,0,sizeof(infected));
for(pii hive:hives){
q.insert({{s,1},hive});
infected[hive.first][hive.second]=1;
}
while(q.size()){
auto [data,pos]=(*q.begin());
q.erase(q.begin());
if(g[pos.first][pos.second]=='D'){
return 1;
}
if(data.second){
//cerr<<"bee at "<<pos.first<<" "<<pos.second<<"\n";
for(int x:{1,-1}){
if(g[pos.first+x][pos.second]=='G'&&!infected[pos.first+x][pos.second]){
q.insert({{data.first+s,1},{pos.first+x,pos.second}});
infected[pos.first+x][pos.second]=1;
}
if(g[pos.first][pos.second+x]=='G'&&!infected[pos.first][pos.second+x]){
q.insert({{data.first+s,1},{pos.first,pos.second+x}});
infected[pos.first][pos.second+x]=1;
}
}
}else if(!infected[pos.first][pos.second]){
//cerr<<"at "<<pos.first<<" "<<pos.second<<"\n";
for(int x:{1,-1}){
if((g[pos.first+x][pos.second]=='G'||g[pos.first+x][pos.second]=='D')&&!infected[pos.first+x][pos.second]){
q.insert({{data.first+1,0},{pos.first+x,pos.second}});
}//else cerr<<"oof "<<pos.first+x<<" "<<pos.second<<" "<<(g[pos.first+x][pos.second]=='G'||g[pos.first+x][pos.second]=='D')<<"\n";
if(g[pos.first][pos.second+x]=='G'||g[pos.first][pos.second+x]=='D'&&!infected[pos.first][pos.second+x]){
q.insert({{data.first+1,0},{pos.first,pos.second+x}});
}//else cerr<<"oof "<<pos.first<<" "<<pos.second+x<<" "<<(g[pos.first][pos.second+x]=='G'||g[pos.first][pos.second+x]=='D')<<"\n";
}
}
infected[pos.first][pos.second]=1;
}
return 0;
}
void solve(){
cin>>n>>s;
g[0]=g[n+1]=string(n,'T');
for(int i=1;i<=n;i++){
cin>>g[i];
g[i]="T"+g[i]+"T";
}
int count=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g[i][j]=='G'){
count++;
}
if(g[i][j]=='H'){
hives.pb({i,j});
}
if(g[i][j]=='M'){
bear={i,j};
}
}
}
int l=0,r=count,ans=-1;
while(l<=r){
//r=0;
int m=(l+r)/2;
if(check(m)){
ans=m;
l=m+1;
}else{
//cerr<<"failed "<<m<<"\n";
r=m-1;
}
}
cout<<ans<<"\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
/*
freopen("atlarge.in","r",stdin);
freopen("atlarge.out","w",stdout);
*/
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
