#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
#define int long long int
#define pb push_back
#define mid (l+(r-l)/2)
#define f first
#define s second
static const int N=805;
static const int MOD=(1LL<<61)-1;
static const int inf=N*N+5;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
void io(string name = ""){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
int n,s,mx,my,hx,hy;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
vector<vector<char>>v(N,vector<char>(N));
vector<vector<int>>bee(N,vector<int>(N,inf));
vector<vector<int>>mec(N,vector<int>(N,inf));
vector<vector<bool>>vis(N,vector<bool>(N,0));
bool inside(int i,int j){ return ((i>0&&i<=n) && (j>0&&j<=n) && (v[i][j]=='M' || v[i][j]=='G'));}
void calcbee(){
queue<array<int,3>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(v[i][j]=='H'){q.push({i,j,0});bee[i][j]=0;}
}
}
while(q.size()){
array<int,3>c=q.front();
q.pop();
// if(bee[c[0]][c[1]]!=inf){continue;}
for(int i=0;i<4;i++){
int cx=c[0]+dx[i],cy=c[1]+dy[i];
if(inside(cx,cy)&& bee[cx][cy]>c[2]+1){
bee[cx][cy]=c[2]+1;
q.push({cx,cy,c[2]+1});
}
}
}
}
void mecho(int k){
mec[mx][my]=k;
queue<array<int,3>>q;
q.push({mx,my,k});
while(q.size()){
array<int,3>c=q.front();
q.pop();
if(vis[c[0]][c[1]]){continue;}
// cout<<'a';
vis[c[0]][c[1]]=1;
for(int i=0;i<4;i++){
int cx=c[0]+dx[i],cy=c[1]+dy[i];
// cout<<c[2]/s<<" ";
if(inside(cx,cy) && mec[cx][cy]>c[2]+1 && (int)(c[2])/s < bee[cx][cy]){
mec[cx][cy]=c[2]+1;
q.push({cx,cy,c[2]+1});
}
}
}
}
int32_t main(){
//io("local");
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>s;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>v[i][j];
if(v[i][j]=='M'){mx=i,my=j;}
if(v[i][j]=='D'){hx=i,hy=j;}
}
}
calcbee();
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<bee[i][j]<<" ";
// }cout<<endl;
// }
int l=0,r=n*n;
bool aaa=0;
while(l<=r){
for(int i=1;i<=n;i++){fill(mec[i].begin(),mec[i].end(),inf);}
for(int i=1;i<=n;i++){fill(vis[i].begin(),vis[i].end(),0);}
mecho(mid*s);
bool chc=0;
for(int i=0;i<n;i++){
int cx=hx+dx[i],cy=hy+dy[i];
if(inside(cx,cy) && vis[cx][cy]){chc=1;aaa=1;}
}
// cout<<mid<<" "<<chc<<endl;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<mec[i][j]<<" ";
// }cout<<endl;
// }
if(chc){l=mid+1;}
else{r=mid-1;}
}
if(aaa){cout<<l-1;}
else{cout<<-1;}
return 0;
}
