#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define LSOne(S) ((S)&(-S))
#define all(S) S.begin(),S.end()
#define fore(V,I,F) for(int V=I;V<=F;V++)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
vpii mov = {{0,1},{1,0},{0,-1},{-1,0}};
struct nodoCola{
int y, x;
int t;
};
void abejitas(vector<string> &mapa, vvi &tiempo, int inc = 1){
queue<nodoCola> cola;
vvb visto(mapa.size(), vb(mapa[0].size()));
fore(i,0,mapa.size()-1){
fore(j,0,mapa.size()-1){
if(mapa[i][j] == 'H'){cola.push({i,j,inc});visto[i][j] = 1;}
}
}
nodoCola act;
while(!cola.empty()){
act = cola.front();
cola.pop();
for(auto [y,x]: mov){
int sy = act.y + y;
int sx = act.x + x;
if(sy < 0 || sx < 0 || sy >=mapa.size() || sx >= mapa[0].size())continue;
if(visto[sy][sx] || (mapa[sy][sx] != 'G' && mapa[sy][sx] != 'M'))continue;
visto[sy][sx] = 1;
tiempo[sy][sx] = act.t + inc;
cola.push({sy,sx,act.t + inc});
}
}
}
int ey,ex,sy,sx;
bool osito( vector<string> &mapa, vvi &tiempo, int k){
queue<nodoCola> cola;
vvb visto(mapa.size(), vb(mapa[0].size()));
cola.push({ey,ex, k});
nodoCola act;
visto[ey][ex] = 1;
while(!cola.empty()){
act = cola.front();
cola.pop();
for(auto [y,x]: mov){
int sy = act.y + y;
int sx = act.x + x;
if(sy < 0 || sx < 0 || sy >=mapa.size() || sx >= mapa[0].size())continue;
if(visto[sy][sx] || (mapa[sy][sx] != 'G' && mapa[sy][sx] != 'D'))continue;
visto[sy][sx] = 1;
if(mapa[sy][sx] == 'D')return true;
if(tiempo[sy][sx] < act.t + 1)continue;
cola.push({sy,sx,act.t+1});
}
}
return false;
}
int solve(){
int n,s;
cin >> n >> s;
vector<string> mapa(n);
fore(i,0,n-1) cin >> mapa[i];
vvi tiempo(mapa.size(), vi(mapa.size()));
abejitas(mapa, tiempo, s);
fore(i,0,n-1){
fore(j,0,n-1){
if(mapa[i][j] == 'M'){
ey = i;
ex = j;
}
if(mapa[i][j] == 'D'){
sy = i;
sx = j;
}
}
}
int l = 0;
//int r = tiempo[ey][ex] / s - 1;
int r = tiempo[ey][ex];
int med = 0;
while(l < r){
med = (l+r)/2 + 1;
if(med * s < tiempo[ey][ex] && osito(mapa, tiempo, med * s)){
l = med;
}else{
r = med-1;
}
}
l--;
return l;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cout << solve() << "\n";
}
