#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<vector<bool>> visited;
vector<vector<int>> dist;
vector<vector<char>> grid;
vector<vector<int>> beeT;
pair<int,int> home;
pair<int,int> bear;
int N,S;
bool f(int t){
priority_queue<pair<int,pair<int,int>>> q;
visited.clear();
dist.clear();
visited.resize(N,vector<bool>(N,false));
dist.resize(N,vector<int>(N,1e14));
dist[bear.first][bear.second]=t*S;
q.push({-t*S,bear});
while(!q.empty()){
int x=q.top().second.first,y=q.top().second.second; q.pop();
if((dist[x][y])/S>=beeT[x][y]&&grid[x][y]!='D') continue;
if(visited[x][y]) continue;
visited[x][y]=true;
if(x-1>=0&&(grid[x-1][y]=='G'||grid[x-1][y]=='M'||grid[x-1][y]=='D')&&dist[x][y]+1<dist[x-1][y]){
dist[x-1][y]=dist[x][y]+1;
q.push({-dist[x-1][y], {x-1,y}});
}
if(x+1<N&&(grid[x+1][y]=='G'||grid[x+1][y]=='M'||grid[x+1][y]=='D')&&dist[x][y]+1<dist[x+1][y]){
dist[x+1][y]=dist[x][y]+1;
q.push({-dist[x+1][y], {x+1,y}});
}
if(y-1>=0&&(grid[x][y-1]=='G'||grid[x][y-1]=='M'||grid[x][y-1]=='D')&&dist[x][y]+1<dist[x][y-1]){
dist[x][y-1]=dist[x][y]+1;
q.push({-dist[x][y-1], {x,y-1}});
}
if(y+1<N&&(grid[x][y+1]=='G'||grid[x][y+1]=='M'||grid[x][y+1]=='D')&&dist[x][y]+1<dist[x][y+1]){
dist[x][y+1]=dist[x][y]+1;
q.push({-dist[x][y+1], {x,y+1}});
}
}
return visited[home.first][home.second];
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> S;
grid.resize(N,vector<char>(N));
visited.resize(N,vector<bool>(N,false));
for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cin >> grid[i][j]; }
for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++){
if(grid[i][j]=='M') bear={i,j};
else if(grid[i][j]=='D') home={i,j};
}
}
beeT.resize(N,vector<int>(N,1e14));
priority_queue<pair<int,pair<int,int>>> q;
for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) if(grid[i][j]=='H') { q.push({0,{i,j}}); beeT[i][j]=0; }}
while(!q.empty()){
int x=q.top().second.first,y=q.top().second.second; q.pop();
if(visited[x][y]) continue;
visited[x][y]=true;
if(x-1>=0&&(grid[x-1][y]=='G'||grid[x-1][y]=='M')&&beeT[x][y]+1<beeT[x-1][y]){
beeT[x-1][y]=beeT[x][y]+1;
q.push({-beeT[x-1][y], {x-1,y}});
}
if(x+1<N&&(grid[x+1][y]=='G'||grid[x+1][y]=='M')&&beeT[x][y]+1<beeT[x+1][y]){
beeT[x+1][y]=beeT[x][y]+1;
q.push({-beeT[x+1][y], {x+1,y}});
}
if(y-1>=0&&(grid[x][y-1]=='G'||grid[x][y-1]=='M')&&beeT[x][y]+1<beeT[x][y-1]){
beeT[x][y-1]=beeT[x][y]+1;
q.push({-beeT[x][y-1], {x,y-1}});
}
if(y+1<N&&(grid[x][y+1]=='G'||grid[x][y+1]=='M')&&beeT[x][y]+1<beeT[x][y+1]){
beeT[x][y+1]=beeT[x][y]+1;
q.push({-beeT[x][y+1], {x,y+1}});
}
}
int l=0,r=1e9;
while(l<r){
int mid=(l+r+1)/2;
if(f(mid)){
l=mid;
}else{
r=mid-1;
}
}
if(!f(0)) cout << -1 << "\n";
else cout << l << "\n";
return 0;
}
