#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> pi;
typedef pair<ll , ll> pll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define F first
#define S second
#define nd "\n"
#define forad(i , a , b) for(int i = a; i < (int) b; i++)
#define forat(i , a , b) for(int i = a; i >= b; i--)
#define debug(x) cout << #x << " = " << x << nd
#define debugv(x , s) cout << #x << " = " << forad(i , 0 , s) cout << x[i] << " "; cout << nd
#define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x) x.begin() , x.end()
const ll mod = 1e9+7 , INF = 1e9;
ll inv(ll x){return x <= 1 ? x : (mod - mod/x) * inv(mod%x) % mod;}
#define smod(a , b) (a%mod+b%mod)%mod
#define rmod(a , b) (a%mod - b%mod + mod)%mod
#define mmod(a , b) (a%mod) * (b%mod)%mod
#define dmod(a , b) (a%mod) * inv(b) %mod
int n, s;
vector<string> a;
queue<pi> cola;
vvi dist;
void moverse(int fromi, int fromj, int toi, int toj) {
if (dist[fromi][fromj] + 1 < dist[toi][toj]) {
cola.push({toi, toj});
dist[toi][toj] = dist[fromi][fromj] + 1;
}
}
void ffm() {
int k = cola.size();
while (k--) {
pi front = cola.front();
cola.pop();
int i = front.first , j = front.second;
if (i > 0) moverse(i, j, i-1, j);
if (j > 0) moverse(i, j, i, j-1);
if (i < n-1) moverse(i, j, i+1, j);
if (j < n-1) moverse(i, j, i, j+1);
}
}
bool cumple(int x,int y){return a[x][y]=='G' || a[x][y]=='M';}
bool puedo(int mt,int bt){return mt/s < bt;}
void ir(int acx,int acy,int irx,int iry, vvi bt, int w){
if(!cumple(acx , acy)) return;
if(bt >= dist[actx][acty]) return;
int aux = bt[actx][acty] - w;
if(puedo(bt , aux)){
dist[acx][acy] = bt;
cola.push({acx , acy});
}
}
vvi bees(vector<pi> h){
dist.assign(n, vi(n, INF));
while(!cola.empty()) cola.pop();
for(auto x : h){
dist[x.F][x.S] = 0;
cola.push(x);
}
while(!cola.empty()) ffm();
return dist;
}
bool mecho_ff(int acx,int acy,int irx,int iry, vvi bt, int w){
dist.assign(n, vi(n, INF));
while(!cola.empty()) cola.pop();
if(bt[acx][acy] <= w) return false;
dist[acx][acy] = 0;
cola.push({acx,acy});
while(!cola.empty()){
int k = cola.size();
while(k--){
auto[x,y] = cola.front(); cola.pop();
int nt = dist[x][y] + 1;
if(x>0) ir(x-1,y);
if(y>0) ir(x,y-1);
if(x<n-1) ir(x+1,y);
if(y<n-1) ir(x,y+1);
}
}
int dx[4]={-1,0,1,0}, dy[4]={0,-1,0,1};
forad(i,0,4){
int nx=irx+dx[i], ny=iry+dy[i];
if(nx<0||ny<0||nx>=n||ny>=n) continue;
if(!cumple(nx,ny)) continue;
if(dist[nx][ny]==INF) continue;
if(puedo(dist[nx][ny], bt[nx][ny]-w)) return true;
}
return false;
}
int main(){
faster;
cin >> n >> s;
a.resize(n);
forad(i,0,n) cin >> a[i];
int acx , acy , irx , iry;
vector<pi> h;
forad(i,0,n){
forad(j,0,n){
if(a[i][j]=='M') acx=i,acy=j;
else if(a[i][j]=='H') h.pb({i,j});
else if(a[i][j]=='D') irx=i,iry=j;
}
}
auto bt = bees(h);
int l = 0, r = n*n, m;
while(l<=r){
m = l + (r-l)/2;
if(mecho_ff(acx,acy,irx,iry,bt,mid)) l = m+1;
else r = mid-1;
}
cout << l << nd;
}
