#include<bits/stdc++.h>
using namespace std;
const int maxn = 805, INF = 0x3f3f3f3f;
#define pii pair<int, int>
#define ff first
#define ss second
int dist[maxn][maxn];
bool valid1[maxn][maxn];
pii ini, fim;
vector<pii> hives;
int px[4] = {1, -1, 0, 0}, py[4] = {0, 0, 1, -1};
int n, s;
bool solve(int T){
bool valid[maxn][maxn];
for(int i = 0; i < maxn; i++){
for(int j = 0; j < maxn; j++) valid[i][j] = valid1[i][j];
}
memset(dist, 0, sizeof dist);
queue<pii> qabel, qurso;
for(pii x : hives)
qabel.push(x);
bool found = false, fuck = false;
while(!qabel.empty()){
int x, y;
tie(x, y) = qabel.front();
if(dist[x][y]==T) break;
qabel.pop();
for(int i = 0; i < 4; i++){
int vx = x + px[i];
int vy = y + py[i];
if(make_pair(vx, vy) == fim) {fuck = true; break;}
if(valid[vx][vy]) dist[vx][vy] = dist[x][y]+1, valid[vx][vy]=false, qabel.push({vx, vy});
}
if(fuck) break;
}
if(fuck) return false;
if(valid[ini.ff][ini.ss]) qurso.push(ini);
int cnt = 0;
while(true){
while(!qurso.empty()){// bfs urso
int x, y;
tie(x, y) = qurso.front();
if(make_pair(x, y)==fim) {found = true; break;}
int distu = dist[x][y];
if(distu%s==0 && distu!=cnt*s) break;
qurso.pop();
for(int i = 0; i < 4; i++){
int vx = x + px[i];
int vy = y + py[i];
if(valid[vx][vy]) dist[vx][vy] = dist[x][y]+1, valid[vx][vy] = false, qurso.push({vx, vy});
}
}
cnt++;
if(qurso.empty() || found) break;
while(!qabel.empty()){// bfs abelhas
int x, y;
tie(x, y) = qabel.front();
if(dist[x][y]==cnt+T) break;
qabel.pop();
for(int i = 0; i < 4; i++){
int vx = x + px[i];
int vy = y + py[i];
if(make_pair(vx, vy) == fim) {fuck = true; break;}
if(valid[vx][vy]) dist[vx][vy] = dist[x][y]+1, valid[vx][vy]=false, qabel.push({vx, vy});
}
if(fuck) break;
}
if(fuck) break;
}
if(fuck) {cout << "fuck\n"; return false;}
else return found;
}
int main(){
cin >> n >> s;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
char c; cin >> c;
if(c=='H') hives.push_back({i, j});
if(c=='M') ini = {i, j};
if(c=='D') fim = {i, j};
if(c=='M' || c=='G' || c=='D') valid1[i][j] = true;
}
}
int l=0, r = n*n, ans = INF;
while(l<=r){
int mid = (l+r)>>1;
if(solve(mid)) l = mid+1, ans = mid;
else r = mid-1;
}
cout << (ans==INF? -1 : ans) << '\n';
}
