//gpt4 debugging
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
static const int MAXN = 800;
static const int INF = 0x3f3f3f3f;
int n, S;
char grid[MAXN][MAXN];
int vis_bee[MAXN][MAXN];
bool vis_mecho[MAXN][MAXN];
pii st, ed;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
// Can bees spread into (x,y)? They start on 'H' and then only spread into grass 'G' or Mecho's start 'M'.
// They cannot enter trees 'T', home 'D', or hive cells beyond the initial sources.
bool valid_bee(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n) return false;
char ch = grid[x][y];
return (ch == 'G' || ch == 'M');
}
// Can Mecho step into (x,y)? He can move on grass 'G', his start 'M', or home 'D', but not on trees 'T' or hives 'H'.
bool valid_mecho(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n) return false;
char ch = grid[x][y];
return (ch == 'G' || ch == 'M' || ch == 'D');
}
// After waiting `wait` full minutes at st, can Mecho reach ed before bees catch him?
bool check(int wait) {
// queue entries: { x, y, minute, steps_used_in_current_minute }
queue<array<int,4>> q;
q.push({st.first, st.second, wait, 0});
memset(vis_mecho, 0, sizeof(vis_mecho));
vis_mecho[st.first][st.second] = true;
while (!q.empty()) {
auto [x, y, minute, used] = q.front();
q.pop();
if (x == ed.first && y == ed.second) return true;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (!valid_mecho(nx, ny)) continue;
int nused = used + 1;
int nminute = minute;
if (nused > S) {
// move into next minute
nused = 1;
nminute++;
}
// if bees arrive at or before nminute, it's unsafe
if (vis_bee[nx][ny] <= nminute) continue;
if (vis_mecho[nx][ny]) continue;
vis_mecho[nx][ny] = true;
q.push({nx, ny, nminute, nused});
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> S;
queue<pii> qb;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
if (grid[i][j] == 'H') {
vis_bee[i][j] = 0;
qb.push({i, j});
} else {
vis_bee[i][j] = INF;
}
if (grid[i][j] == 'M') st = {i, j};
if (grid[i][j] == 'D') ed = {i, j};
}
}
// Multi-source BFS from hives to compute arrival times of bees
while (!qb.empty()) {
auto [x, y] = qb.front(); qb.pop();
int t = vis_bee[x][y];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (!valid_bee(nx, ny)) continue;
if (vis_bee[nx][ny] > t + 1) {
vis_bee[nx][ny] = t + 1;
qb.push({nx, ny});
}
}
}
// Binary search the maximum waiting time
int lo = 0, hi = n * n, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << ans << "\n";
return 0;
}
