//grok debugging
#include <bits/stdc++.h>
using namespace std;
const int mxN = 8e2;
char c[mxN][mxN];
int vis[mxN][mxN];
bool vis1[mxN][mxN];
pair<int, int> st, ed;
int n, s;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool mecho_valid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n &&
(c[x][y] == 'G' || c[x][y] == 'M' || c[x][y] == 'D');
}
bool bee_valid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n &&
(c[x][y] == 'G' || c[x][y] == 'M');
}
bool check(int x) {
if (vis[st.first][st.second] <= x) return 0; // Bees reach 'M' during eating
queue<array<int, 4>> q; // {x, y, minute, steps_in_minute}
q.push({st.first, st.second, x + 1, 0});
memset(vis1, 0, sizeof(vis1));
vis1[st.first][st.second] = 1;
while (!q.empty()) {
auto [xx, yy, step, state] = q.front();
q.pop();
if (xx == ed.first && yy == ed.second) return 1;
for (int i = 0; i < 4; i++) {
int nx = xx + dx[i], ny = yy + dy[i];
if (mecho_valid(nx, ny) && vis[nx][ny] > step && !vis1[nx][ny]) {
vis1[nx][ny] = 1;
if (state + 1 == s) {
q.push({nx, ny, step + 1, 0});
} else {
q.push({nx, ny, step, state + 1});
}
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> s;
queue<array<int, 3>> q;
memset(vis, 0x3f, sizeof(vis));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> c[i][j];
if (c[i][j] == 'M') st = {i, j};
if (c[i][j] == 'D') ed = {i, j};
if (c[i][j] == 'H') q.push({i, j, 0}), vis[i][j] = 0;
}
}
while (!q.empty()) {
auto [x, y, now] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (bee_valid(nx, ny) && vis[nx][ny] == 0x3f3f3f3f) {
vis[nx][ny] = now + 1;
q.push({nx, ny, now + 1});
}
}
}
int l = 0, r = n * n, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << "\n";
return 0;
}
