#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <math.h>
using namespace std;
#define endl "\n"
#define int int64_t
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR0(i,a) FOR(i,0,a)
#define FOR1(i,a) for (int i = (1); i <= (a); ++i)
#define TRAV(a,x) for (auto& a: x)
using pii = pair<int,int>;
using vi = vector<int>;
vi dx = {-1,0,1,0};
vi dy = {0,-1,0,1};
const int NMAX=80;
int N;
int S;
pii start={0,0};
pii end2={0,0};
bool f(int k,string grid[NMAX][NMAX],int distBees[NMAX][NMAX]){
queue<pii> cur;
cur.push(start);
int dist[N][N];
FOR0(i,N){
FOR0(j,N){
dist[i][j]=-1;
}
}
dist[start.first][start.second]=0;
while(!cur.empty()){
pii curNode=cur.front();
cur.pop();
FOR0(i,4){
int newR=curNode.first+dx[i];
int newC=curNode.second+dy[i];
if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
if((grid[newR][newC]=="G" || grid[newR][newC]=="D") && dist[newR][newC]==(-1)){
if((distBees[newR][newC]-k)>((dist[curNode.first][curNode.second]+1)/S)){
//cout<<newR<<" "<<newC<<endl;
dist[newR][newC]=dist[curNode.first][curNode.second]+1;
cur.push({newR,newC});
}
}
}
}
bool ans=false;
FOR0(i,4){
int newR=end2.first+dx[i];
int newC=end2.second+dy[i];
if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
if((grid[newR][newC]=="G" || grid[newR][newC]=="D") && dist[newR][newC]!=(-1)){
//cout<<newR<<" "<<newC<<endl;
ans=true;
}
}
return ans;
}
int last_true(int lo, int hi,string grid[NMAX][NMAX],int distBees[NMAX][NMAX]) {
// if none of the values in the range work, return lo - 1
lo--;
while (lo < hi) {
// find the middle of the current range (rounding up)
int mid = lo + (hi - lo + 1) / 2;
if (f(mid,grid,distBees)) {
// if mid works, then all numbers smaller than mid also work
lo = mid;
} else {
// if mid does not work, greater values would not work either
hi = mid - 1;
}
}
return lo;
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// cout<<"yo"<<endl;
// return 0;
cin>>N>>S;
string grid[NMAX][NMAX];
int distBees[NMAX][NMAX];
queue<pii> cur;
FOR0(r,N){
string in;
cin>>in;
FOR0(c,N){
distBees[r][c]=-1;
grid[r][c]=(in.at(c));
if(grid[r][c]=="H"){
cur.push({r,c});
distBees[r][c]=0;
}
if(grid[r][c]=="M"){
start={r,c};
}
if(grid[r][c]=="D"){
end2={r,c};
}
}
}
// return 0;
while(!cur.empty()){
pii curNode=cur.front();
int curR=curNode.first;
int curC=curNode.second;
cur.pop();
FOR0(i,4){
int newR=curNode.first+dx[i];
int newC=curNode.second+dy[i];
if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
if(grid[newR][newC]!="M" && distBees[newR][newC]==(-1)){
distBees[newR][newC]=distBees[curR][curC]+1;
cur.push({newR,newC});
}
}
}
//return 0;
int ans=last_true(0,100000000,grid,distBees);
if(ans==100000000){
ans=-1;
}
cout<<ans<<endl;
return 0;
}
