#include "bits/stdc++.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, x; cin >> n >> x;
vector<string> ma(n); for (auto &x : ma) cin >> x;
vector<pii> h;
pii s, t;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (ma[i][j] == 'M')
s = {i, j};
else if (ma[i][j] == 'D')
t = {i, j};
else if (ma[i][j] == 'H')
h.push_back({i, j});
auto val = [&](int i, int j) -> bool {
return 0 <= i && i < n && 0 <= j && j < n && (ma[i][j] == 'G' || ma[i][j] == 'M');
};
auto val_time = [&](int a, int b) -> bool {
return a / x < b;
};
auto check = [&](int k) -> bool {
vector bees_vis(n, vector<bool>(n));
vector mecho_vis(n, vector<bool>(n));
vector bees_time(n, vector<int>(n));
vector mecho_time(n, vector<int>(n));
queue<pii> q;
for (auto [i, j] : h) {
q.push({i, j});
bees_vis[i][j] = true;
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (val(nx, ny) && !bees_vis[nx][ny]) {
q.push({nx, ny});
bees_vis[nx][ny] = true;
bees_time[nx][ny] = bees_time[x][y] + 1;
}
}
}
q.push(s);
mecho_vis[s.first][s.second] = true;
if (bees_time[s.first][s.second] <= k) q.pop();
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (val(nx, ny) && !mecho_vis[nx][ny] && val_time(mecho_time[x][y] + 1, bees_time[nx][ny] - k)) {
q.push({nx, ny});
mecho_vis[nx][ny] = true;
mecho_time[nx][ny] = mecho_time[x][y] + 1;
}
}
}
bool ok = false;
for (int i = 0; i < 4; i++) {
int nx = t.first + dx[i];
int ny = t.second + dy[i];
if (val(nx, ny) && mecho_vis[nx][ny] && val_time(mecho_time[nx][ny], bees_time[nx][ny] - k))
ok = true;
}
return ok;
};
int l = -1; // l is good
int r = n * n; // r is bad
while (r > l + 1) {
int m = (l + r) / 2;
check(m) ? l = m : r = m;
}
cout << l << nl;
return 0;
}
