#include <bits/stdc++.h>
using namespace std;
const int N=805, inf=1e9;
const int dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
int n, s, dist1[N][N], dist2[N][N], xM, yM, xD, yD;
pair<int,int> trace[N][N];
string mat[N];
struct state{
int times, steps, x, y;
bool operator<(const state other)const{
return times>other.times;
}
};
bool valid(int x,int y){
return x>=0 && x<n && y>=0 && y<n;
}
void bfs(int sx,int sy){
dist1[sx][sy]=1;
queue<pair<int,int>> q;
q.push({sx,sy});
while (q.size()){
auto [x, y]=q.front();
q.pop();
for (int i=0;i<4;i++){
int nx=x+dx[i], ny=y+dy[i];
if (valid(nx,ny) && mat[nx][ny]=='G' && dist1[nx][ny]>dist1[x][y]+1){
dist1[nx][ny]=dist1[x][y]+1;
q.push({nx,ny});
}
}
}
}
bool dijkstra(int sx,int sy,int delay){
trace[sx][sy]={-1,-1};
priority_queue<state> pq;
pq.push({delay,0,sx,sy});
dist2[sx][sy]=0;
while (pq.size()){
auto [times, steps, x, y]=pq.top();
pq.pop();
if (dist1[x][y]<=dist2[x][y]+delay) continue;
if (mat[x][y]=='D'){
return true;
}
for (int i=0;i<4;i++){
int ns=steps+1;
int nt=ceil((double) ns/s);
int nx=x+dx[i], ny=y+dy[i];
if (valid(nx,ny) && (mat[nx][ny]=='G' || mat[nx][ny]=='D') && dist2[nx][ny]>nt){
dist2[nx][ny]=nt;
pq.push({nt,ns,nx,ny});
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>s;
for (int i=0;i<n;i++) cin>>mat[i];
fill(&dist1[0][0],&dist1[0][0]+N*N,inf);
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
if (mat[i][j]=='M'){
xM=i;
yM=j;
}
if (mat[i][j]=='H') bfs(i,j);
if (mat[i][j]=='D'){
xD=i;
yD=j;
}
}
}
int l=0, r=n*n, ans=0;
while (l<=r){
int mid=(l+r)>>1;
fill(&dist2[0][0],&dist2[0][0]+N*N,inf);
if (dijkstra(xM,yM,mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans;
return 0;
}
