#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int INF = 1e9;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, S;
if(!(cin >> n >> S)) return 0;
vector<string> a(n);
for(int i=0;i<n;i++) cin >> a[i];
int sx=-1, sy=-1, tx=-1, ty=-1;
vector<pii> hives;
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(a[i][j] == 'H'){ hives.push_back({i,j}); }
}
}
// bees_time: minute when bees first occupy cell (hive = 0). D is not enterable -> keep INF.
vector<vector<int>> bees(n, vector<int>(n, INF));
queue<pii> q;
for(auto &h : hives){
bees[h.first][h.second] = 0;
q.push(h);
}
while(!q.empty()){
auto [x,y] = q.front(); q.pop();
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 can spread only into grassy cells (G or M initially). not into T or D or H again.
if(a[nx][ny] == 'G' || a[nx][ny] == 'M'){
if(bees[nx][ny] == INF){
bees[nx][ny] = bees[x][y] + 1;
q.push({nx, ny});
}
}
}
}
// Note: bees[tx][ty] stays INF because bees cannot enter D.
// check(t): can Mecho wait t minutes then still reach D?
auto can = [&](int t)->bool{
if(bees[sx][sy] <= t) return false; // bees already reach honey while Mecho still there
vector<vector<char>> seen(n, vector<char>(n, 0));
queue<pii> curr;
curr.push({sx, sy});
seen[sx][sy] = 1;
int time = t; // bees have occupied all cells with bees[..] <= time
while(!curr.empty()){
// within this minute, Mecho can move up to S steps.
// BFS-limited to depth S starting from all nodes in curr (multi-source).
queue<pair<pii,int>> bfsq;
vector<vector<char>> inbfs(n, vector<char>(n, 0));
// push all current positions as starting nodes (depth 0)
int sz = (int)curr.size();
while(sz--){
auto p = curr.front(); curr.pop();
int x = p.first, y = p.second;
// If Mecho at any time inside minute reaches home, succeed immediately.
if(x == tx && y == ty) return true;
// Note: we should allow starting positions only if not currently occupied by bees:
if(bees[x][y] <= time) continue; // already unsafe at start of minute
bfsq.push({{x,y}, 0});
inbfs[x][y] = 1;
}
queue<pii> next; // positions Mecho can be at end of this minute
while(!bfsq.empty()){
auto cur = bfsq.front(); bfsq.pop();
int x = cur.first.first, y = cur.first.second, d = cur.second;
// If he steps onto D at any time -> safe immediately
if(x == tx && y == ty) return true;
// he can stand here at end of minute only if bees won't reach it at end of minute
if(bees[x][y] > time + 1 && !seen[x][y]){
next.push({x,y});
seen[x][y] = 1;
}
if(d == S) continue;
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;
if(inbfs[nx][ny]) continue;
// Mecho can travel on G or D (and M originally treated as G)
if(!(a[nx][ny] == 'G' || a[nx][ny] == 'D' || a[nx][ny] == 'M')) continue;
// cannot step into a cell that bees already occupy at start of this minute
if(bees[nx][ny] <= time) continue;
inbfs[nx][ny] = 1;
bfsq.push({{nx,ny}, d+1});
}
}
// advance minute
time++;
// prepare for next minute
curr = move(next);
}
return false;
};
// binary search maximum t (minutes) such that can(t) == true
int l = 0, r = 2*n; // as argued, 2*n is safe upper bound in minutes
int 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;
}
