#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,a,b) for(int i=a; i<(b); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;
const int four[5]={0,1,0,-1,0};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll s;
cin>>n>>s;
vector<string> forest(n);
rep(i,n){
cin>>forest[i];
}
vector<vector<ll>> bee(n,vector<ll>(n,INF));
queue<pair<int,int>> vert;
rep(i,n){
rep(j,n){
if(forest[i][j]=='H'){
bee[i][j]=0;
vert.push({i,j});
}
}
}
while(!vert.empty()){
int x,y;
tie(x,y)=vert.front();
vert.pop();
rep(i,4){
int nx=x+four[i],ny=y+four[i+1];
if(nx<0 or n<=nx or ny<0 or n<=ny){
continue;
}
if(forest[nx][ny]!='G'){
continue;
}
if(bee[nx][ny]>bee[x][y]+1){
bee[nx][ny]=bee[x][y]+1;
vert.push({nx,ny});
}
}
}
int hx,hy;
rep(i,n){
rep(j,n){
if(forest[i][j]=='D'){
hx=i;
hy=j;
}
}
}
ll ok=-1,ng=n*n+1000;
vector<vector<ll>> dist(n,vector<ll>(n));
while(ng-ok>1){
ll mid=(ok+ng)>>1;
rep(i,n){
rep(j,n){
if(forest[i][j]=='M'){
dist[i][j]=mid*s;
vert.push({i,j});
}
else{
dist[i][j]=INF;
}
}
}
while(!vert.empty()){
int x,y;
tie(x,y)=vert.front();
vert.pop();
rep(i,4){
int nx=x+four[i],ny=y+four[i+1];
if(nx<0 or n<=nx or ny<0 or n<=ny){
continue;
}
if(forest[nx][ny]!='G' and forest[nx][ny]!='D'){
continue;
}
if((dist[x][y]+1)/s>=bee[nx][ny]){
continue;
}
if(dist[nx][ny]>dist[x][y]+1){
dist[nx][ny]=dist[x][y]+1;
vert.push({nx,ny});
}
}
}
if(dist[hx][hy]<INF){
ok=mid;
}
else{
ng=mid;
}
}
cout<<ok<<"\n";
}
