#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N = 805, dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
int n, s;
pair<int, int> src, dest;
vector<string> a(N); vector<vector<int> > dist(N, vector<int> (N, -1));
vector<pair<int, int> > hive; vector<vector<bool> > vis(N, vector<bool> (N, false));
bool ok(int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < n && (a[x][y] == 'G' || a[x][y] == 'M' || a[x][y] == 'D'));
}
bool ok2(int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < n && (a[x][y] == 'G' || a[x][y] == 'M' || a[x][y] == 'H'));
}
struct node {
int x, y, t;
node(int a, int b, int c) {
x = a, y = b, t = c;
}
};
bool check(int t) {
// cout << t << "\n";
if (dist[src.fi][src.se] <= t) return false;
queue<node> q;
for (int i = 0; i < n; i++) { fill(vis[i].begin(), vis[i].end(), false); }
// for (auto& [fi, se] : hive) q.push(node(fi, se, 0)), vis[fi][se] = false;
q.push(node(src.fi, src.se, 0)); vis[src.fi][src.se] = true;
while (!q.empty()) {
auto now = q.front();
q.pop();
// if (t == 24) cout << now.x << " " << now.y << " " << now.t << "\n";
for (int i = 0; i < 4; i++) {
int x = now.x + dx[i];
int y = now.y + dy[i];
// walk first then bees go
// bees are at place (now.t - 1) / s;
if (!ok(x, y)) continue;
if (((now.t + 1) / s) + t >= dist[x][y] && (make_pair(x, y) != dest)) continue;
// cout << now.t / s << " " << dist[x][y] << "\n";
if (!vis[x][y]) {
vis[x][y] = true;
q.push(node(x, y, now.t + 1));
}
}
}
return vis[dest.fi][dest.se];
}
void precompute() {
queue<pair<int, int> > q;
for (int i = 0; i < n; i++) { fill(vis[i].begin(), vis[i].end(), false); }
for (auto& [fi, se] : hive) q.push({fi, se}), vis[fi][se] = true, dist[fi][se] = 0;
while (!q.empty()) {
auto now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = now.fi + dx[i];
int y = now.se + dy[i];
if (!ok2(x, y)) continue;
if (!vis[x][y]) {
vis[x][y] = true;
q.push({x, y});
dist[x][y] = dist[now.fi][now.se] + 1;
}
}
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> s;
for (int i = 0; i < n; i++) {
cin >> a[i];
for (int j = 0; j < n; j++) {
if (a[i][j] == 'M') src = {i, j};
if (a[i][j] == 'H') hive.push_back({i, j});
if (a[i][j] == 'D') dest = {i, j};
}
}
precompute();
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << vis[i][j] << " ";
// }
// cout << "\n";
// }
if (!check(0)) { cout << "-1\n"; return 0; }
int l = 0, r = 1e9;
while (l < r) {
int m = (l + r) >> 1;
if (!check(m)) r = m;
else l = m + 1;
}
cout << l - 1 << "\n";
return 0;
}
