#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define endl "\n"
#define ll long long
//#define int long long
void fopn(string name){
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
const ll INF=1e18,mod=1e9,N=1e7+5;
int n,s;
char a[805][805];
pair<int,int> cur,last;
int dist[805][805][2];
vector<int> dx={1,-1,0, 0},
dy={0, 0,1,-1};
bool okh(int x, int y){
return (x>0 && x<=n && y>0 && y<=n && (a[x][y]=='M' || a[x][y]=='G' || a[x][y]=='H'));
}
bool okm(int x, int y){
return (x>0 && x<=n && y>0 && y<=n && (a[x][y]=='M' || a[x][y]=='G' || a[x][y]=='D'));
}
queue<pair<int,int>> dq;
bool check(int D){
if(dist[cur.fr][cur.sc][0]<=D) return 0;
while(!dq.empty()) dq.pop();
dq.push({cur.fr,cur.sc});
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
dist[i][j][1]=0;
}
dist[cur.fr][cur.sc][1]=1;
while(!dq.empty()){
pair<int,int> a=dq.front();
dq.pop();
for(int i=0;i<4;i++){
int x=a.fr+dx[i],y=a.sc+dy[i];
int d=dist[a.fr][a.sc][1]+1;
if(okm(x,y) && !dist[x][y][1]){
if((d-1)/s+1+D<=dist[x][y][0]){
dq.push({x,y});
dist[x][y][1]=d;
}
if(x==last.fr && y==last.sc && (d-1)/s+D-((d-1)%s==0)<=dist[x][y][0]) return 1;
}
}
}
return dist[last.fr][last.sc][1];
}
void solve(){
queue<pair<int,int>> dq;
cin>>n>>s;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]=='H'){
dq.push({i,j});
dist[i][j][0]=1;
}
else if(a[i][j]=='M')
cur={i,j};
else if(a[i][j]=='D')
last={i,j};
}
}
while(!dq.empty()){
pair<int,int> a=dq.front();
dq.pop();
for(int i=0;i<4;i++){
int x=a.fr+dx[i],y=a.sc+dy[i];
if(okh(x,y) && !dist[x][y][0]){
dist[x][y][0]=dist[a.fr][a.sc][0]+1;
dq.push({x,y});
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j][0]-=(dist[i][j][0]>0);
}
}
dist[last.fr][last.sc][0]=1e9;
int l=-1,r=1e9;
while(l<r){
int md=(l)+(r-l+1)/2;
if(check(md)) l=md;
else r=md-1;
}
cout<<l<<endl;
}
main(){
ios;
int T=1;
//cin>>T;
for(int i=1;i<=T;i++){
//cout<<"Case #"<<i<<": ";
solve();
}
}
