#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N, S;
vector<string> V;
vector<vector<int>> P;
int dirs[4][2] = {{1, 0},{0, 1},{-1, 0},{0, -1}};
struct info{
int r, c, d;
info(){}
info(int _r, int _c, int _d): r(_r), c(_c), d(_d) {}
};
void precompute(vector<pair<int, int>> starts){
queue<info> q;
for(int i = 0; i < (int)starts.size(); i++){
q.push(info(starts[i].first, starts[i].second, 0));
P[starts[i].first][starts[i].second] = 0;
}
while(!q.empty()){
info curr = q.front();
q.pop();
int r = curr.r;
int c = curr.c;
int depth = curr.d;
for(int i = 0; i < 4; i++){
int nr = r + dirs[i][0];
int nc = c + dirs[i][1];
if(nr < 0 || nr >= N || nc < 0 || nc >= N || (V[nr][nc] != 'G' && V[nr][nc] != 'M') || P[nr][nc] != INT_MAX) continue;
P[nr][nc] = depth+1;
q.push(info(nr, nc, depth+1));
}
}
}
bool solver(int r, int c, int dr, int dc, int l){
queue<info> q;
q.push(info(r, c, l+1));
vector<vector<bool>> visited(N, vector<bool>(N, false));
while(!q.empty()){
info curr = q.front();
q.pop();
int r = curr.r;
int c = curr.c;
int depth = curr.d;
// cout<<"DEBUG-->"<<l<<" "<<r<<" "<<c<<endl;
visited[r][c] = true;
for(int i = 0; i < 4; i++){
int nr = r + dirs[i][0];
int nc = c + dirs[i][1];
if(nr < 0 || nr >= N || nc < 0 || nc >= N || (V[nr][nc] != 'G' && V[nr][nc] != 'D') || visited[nr][nc] || P[nr][nc] <= (l + (int)((depth-l)/S))) continue;
visited[nr][nc] = true;
q.push(info(nr, nc, depth+1));
}
}
return visited[dr][dc];
}
void solve(){
cin>>N>>S;
V.assign(N, "");
P.assign(N, vector<int>(N, INT_MAX));
vector<pair<int, int>> starts;
int sr, sc, dr, dc;
for(int i = 0; i < N; i++){
cin>>V[i];
for(int j = 0; j < N; j++)
if(V[i][j] == 'H') starts.push_back({i, j});
else if(V[i][j] == 'M') sr = i, sc = j;
else if(V[i][j] == 'D') dr = i, dc = j;
}
precompute(starts);
int low = 0;
int high = P[sr][sc];
int ans = -1;
while(low < high){
int mid = low + (high - low)/2;
if(solver(sr, sc, dr, dc, mid)){
ans = mid;
low = mid+1;
}else high = mid;
}
cout<<ans<<endl;
}
int main(){
solve();
}
