#include <iostream>
#include <cstdio>
#include <queue>
#define N 805
#define PR pair<int, int>
#define F first
#define S second
using namespace std;
int n, k, mi, mj, di, dj, v[N][N], x[N][N], y[N][N];
int lt, rt, md, ans;
char a[N][N];
queue<PR> qu;
int dr[4] = {1,0,-1,0};
int dc[4] = {0,1,0,-1};
int f(int p) {
int i, j, r, c, t;
for(i=0; i<n; i++) for(j=0; j<n; j++) v[i][j] = 0;
while(!qu.empty()) qu.pop();
y[mi][mj] = p * k;
if(y[mi][mj] < x[mi][mj]) {
v[mi][mj] = 1;
qu.push({mi, mj});
}
while(!qu.empty()) {
r = qu.front().F;
c = qu.front().S;
qu.pop();
for(t=0; t<4; t++) {
i = r + dr[t];
j = c + dc[t];
if(0<=i && i<n && 0<=j && j<n && y[r][c]+1 < x[i][j] && !v[i][j] && (a[i][j]=='G' || a[i][j]=='D')) {
v[i][j] = 1;
y[i][j] = y[r][c] + 1;
qu.push({i, j});
}
}
}
return v[di][dj];
}
int main() {
int i, j, r, c, t;
cin >> n >> k;
for(i=0; i<n; i++) {
cin >> a[i];
for(j=0; j<n; j++) {
x[i][j] = 1e9;
if(a[i][j]=='H') {
x[i][j] = 0;
v[i][j] = 1;
qu.push({i,j});
}
else if(a[i][j]=='M') mi=i, mj=j;
else if(a[i][j]=='D') di=i, dj=j;
}
}
while(!qu.empty()) {
r = qu.front().F;
c = qu.front().S;
qu.pop();
for(t=0; t<4; t++) {
i = r + dr[t];
j = c + dc[t];
if(0<=i && i<n && 0<=j && j<n && !v[i][j] && (a[i][j]=='G' || a[i][j]=='M')) {
v[i][j] = 1;
x[i][j] = x[r][c] + k;
qu.push({i, j});
}
}
}
rt = n*n;
while(lt <= rt) {
md = lt+rt >> 1;
if(f(md)) ans=md, lt=md+1;
else rt=md-1;
}
cout << ans;
return 0;
}
