#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int MAXN = 805;
const int INF = 1e9;
int n, k;
string a[MAXN];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int bees_time[MAXN][MAXN];
// flattened helpers
inline int id(int x, int y){ return x * n + y; }
inline int xi(int idd){ return idd / n; }
inline int yi(int idd){ return idd % n; }
// compute bees_time once
void compute_bees_time(){
for(int i=0;i<n;i++) for(int j=0;j<n;j++) bees_time[i][j] = INF;
queue<pii> q;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j] == 'H'){
bees_time[i][j] = 0;
q.push({i,j});
}
}
}
while(!q.empty()){
auto cur = q.front(); q.pop();
int x = cur.first, y = cur.second;
for(int dir=0; dir<4; ++dir){
int nx = x + dx[dir], ny = y + dy[dir];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
// bees spread into G or M (treat M like G)
if(!(a[nx][ny]=='G' || a[nx][ny]=='M')) continue;
if(bees_time[nx][ny] == INF){
bees_time[nx][ny] = bees_time[x][y] + 1;
q.push({nx, ny});
}
}
}
// bees_time at D remains INF
}
// Global visit tokens to avoid clearing arrays
static int seen_mark[MAXN*MAXN];
static int inbfs_mark[MAXN*MAXN];
static int seen_token = 1;
static int inbfs_token = 1;
// can(t): Me waits t minutes, can he reach D?
bool can(int t){
int sx=-1, sy=-1, tx=-1, ty=-1;
for(int i=0;i<n;i++) for(int j=0;j<n;j++){
if(a[i][j]=='M'){ sx=i; sy=j; }
if(a[i][j]=='D'){ tx=i; ty=j; }
}
if(sx==-1 || tx==-1) return false;
if(bees_time[sx][sy] <= t) return false;
// curr = flattened positions Me can stand at start of a minute
vector<int> curr;
curr.reserve(n*n);
curr.push_back(id(sx,sy));
++seen_token; if(seen_token==0){ ++seen_token; ++inbfs_token; } // avoid zero wrap
++inbfs_token;
int time = t;
while(!curr.empty()){
// BFS multi-source limited to depth k
// We'll use arrays as circular queue to store nodes and depth
int qsize = n * n + 5;
static int qnodes[MAXN*MAXN];
static int qdepth[MAXN*MAXN];
int qhead = 0, qtail = 0;
++inbfs_token;
if(inbfs_token==0){ ++inbfs_token; ++seen_token; } // safety for wrap
// push all current starts
for(int pos : curr){
int x = xi(pos), y = yi(pos);
if(bees_time[x][y] <= time) continue; // unsafe at start of minute
// immediate success if at D
if(x==tx && y==ty) return true;
if(inbfs_mark[pos] != inbfs_token){
inbfs_mark[pos] = inbfs_token;
qnodes[qtail] = pos;
qdepth[qtail] = 0;
++qtail;
}
}
vector<int> next; next.reserve(n*n/4);
// BFS limited
while(qhead < qtail){
int curpos = qnodes[qhead];
int d = qdepth[qhead];
++qhead;
int x = xi(curpos), y = yi(curpos);
if(x==tx && y==ty) return true;
// can stand here at end of minute if bees arrive later than time+1
if(bees_time[x][y] > time + 1 && seen_mark[curpos] != seen_token){
seen_mark[curpos] = seen_token;
next.push_back(curpos);
}
if(d == k) continue;
// expand neighbors
for(int dir=0; dir<4; ++dir){
int nx = x + dx[dir], ny = y + dy[dir];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
char ch = a[nx][ny];
if(!(ch=='G' || ch=='D' || ch=='M')) continue;
if(bees_time[nx][ny] <= time) continue; // cannot step into bees-occupied at start
int nid = id(nx,ny);
if(inbfs_mark[nid] == inbfs_token) continue;
inbfs_mark[nid] = inbfs_token;
qnodes[qtail] = nid;
qdepth[qtail] = d+1;
++qtail;
}
}
// advance minute
time++;
++seen_token; if(seen_token==0){ ++seen_token; ++inbfs_token; }
curr.swap(next);
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
if(!(cin >> n >> k)) return 0;
for(int i=0;i<n;i++) cin >> a[i];
compute_bees_time();
int l=0, r = n * n, ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(can(mid)){ ans = mid; l = mid + 1; }
else r = mid - 1;
}
cout << ans << '\n';
return 0;
}
