#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using pii = pair<int,int>;
const int N = 810;
const int inf = 7000;
char a[N][N];
int n, s;
int di[] = {-1, 0, 0, 1};
int dj[] = {0, -1, 1, 0};
int si, sj, ti, tj;
int distBee[N][N];
int distMecho[N][N];
bool ok(int t) {
if(t >= distBee[si][sj]) return false;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
distMecho[i][j] = inf;
}
}
distMecho[si][sj] = 0;
queue<pii> q;
q.push({si, sj});
while(!q.empty()) {
int ui = q.front().first, uj = q.front().second;
q.pop();
if(ui == ti && uj == tj) return true;
for(int k = 0; k < 4; k++) {
int vi = ui + di[k], vj = uj + dj[k];
if(vi >= 0 && vi < n && vj >= 0 && vj < n) {
if(a[vi][vj] == 'G' || a[vi][vj] == 'D') {
if(distMecho[vi][vj] > distMecho[ui][uj] + 1) {
int step = distMecho[ui][uj] + 1;
int minute = (step - 1) / s + 1; // ceil division
int totaltime = t + minute;
if(a[vi][vj] != 'D') {
if(totaltime >= distBee[vi][vj]) continue;
}
distMecho[vi][vj] = distMecho[ui][uj] + 1;
q.push({vi, vj});
}
}
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> s;
queue<pii> qb;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
distBee[i][j] = inf;
cin >> a[i][j];
if(a[i][j] == 'H') {
qb.push({i, j});
distBee[i][j] = 0;
}
else if(a[i][j] == 'M') si = i, sj = j;
else if(a[i][j] == 'D') ti = i, tj = j;
}
}
while(!qb.empty()) {
int ui = qb.front().first, uj = qb.front().second;
qb.pop();
for(int k = 0; k < 4; k++) {
int vi = ui + di[k], vj = uj + dj[k];
if(vi >= 0 && vi < n && vj >= 0 && vj < n) {
if((a[vi][vj] == 'G' || a[vi][vj] == 'M') && distBee[vi][vj] > distBee[ui][uj] + 1) {
distBee[vi][vj] = distBee[ui][uj] + 1;
qb.push({vi, vj});
}
}
}
}
int ans = -1;
int l = 0, r = 640010;
while(l <= r) {
int mid = l + (r-l)/2;
if(ok(mid)) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << ans;
return 0;
}
