#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
int n, m;
int C[]{0,1,0,-1}, R[]{1,0,-1,0};
pair<int,int> a, b; queue<pair<int,int>> q;
vector<vector<int>> g(805, vector<int>(805, 1e9));
vector<string> v(805);
bool bfs(int k) {
vector<vector<int>> dis(n, vector<int>(n, 1e9));
q.push(a); dis[a.f][a.s] = 0;
while(!q.empty()) {
pair<int,int> r = q.front(); q.pop();
for(int i=0;i<4;i++) {
int x = r.f+R[i], y = r.s+C[i];
if(0 <= x && x < n && 0 <= y && y < n && ((dis[r.f][r.s]+1)/m < g[x][y]-k && v[x][y] != 'D' || (dis[r.f][r.s]+1)/m <= g[r.f][r.s]-k && v[x][y] == 'D'))
if(dis[r.f][r.s]+1 < dis[x][y] && (v[x][y] == 'G' || v[x][y] == 'D')) {
dis[x][y] = dis[r.f][r.s]+1;
q.push({x,y});
}
}
}
if(dis[b.f][b.s] == 1e9) return false;
return true;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m; for(int i=0;i<n;i++) cin >> v[i];
for(int i=0;i<n;i++) for(int j=0;j<n;j++) {
if(v[i][j] == 'M') a.f = i, a.s = j;
if(v[i][j] == 'D') b.f = i, b.s = j;
if(v[i][j] == 'H') {q.push({i,j}); g[i][j] = 0;}
}
while(!q.empty()) {
pair<int,int> r = q.front(); q.pop();
for(int i=0;i<4;i++) {
int x = r.f+R[i], y = r.s+C[i];
if(0 <= x && x < n && 0 <= y && y < n) if(g[r.f][r.s]+1 < g[x][y] && (v[x][y] == 'G' || v[x][y] == 'M')) {
g[x][y] = g[r.f][r.s]+1;
q.push({x,y});
}
}
}
int l = 0, r = 1e6;
while(l<r) {
int d = (l+r+1)/2;
if(bfs(d)) l = d;
else r = d-1;
}
cout << l;
}
