#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int n, s;
vector<string> grid;
bool valid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n &&
(grid[x][y] == 'G' || grid[x][y] == 'M');
}
bool reached(int mdis, int bdis) { return mdis / s < bdis; }
int main() {
cin >> n >> s;
grid.resize(n);
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
vector<pii> hives;
int mx, my, hx, hy;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'M') {
mx = i, my = j;
} else if (grid[i][j] == 'H') {
hives.push_back({i, j});
} else if (grid[i][j] == 'D') {
hx = i, hy = j;
}
}
}
auto ok = [&](int x) {
vector<vector<bool>> bvis(n, vector<bool>(n)), mvis(n, vector<bool>(n));
vector<vector<int>> btime(n, vector<int>(n)), mtime(n, vector<int>(n));
queue<pii> q;
for (auto i : hives) {
q.push({i.first, i.second});
bvis[i.first][i.second] = true;
}
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny) && !bvis[nx][ny]) {
btime[nx][ny] = btime[x][y] + 1;
q.push({nx, ny});
bvis[nx][ny] = true;
}
}
}
q.push({mx, my});
mvis[mx][my] = true;
if (btime[mx][my] <= x) {
q.pop();
}
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (valid(nx, ny) && !mvis[nx][ny] &&
reached(mtime[x][y] + 1, btime[nx][ny] - x)) {
mvis[nx][ny] = true;
q.push({nx, ny});
mtime[nx][ny] = mtime[x][y] + 1;
}
}
}
bool tmp = false;
for (int i = 0; i < 4; i++) {
int nx = hx + dx[i], ny = hy + dy[i];
if (valid(nx, ny) && reached(mtime[nx][ny], btime[nx][ny] - x) &&
mvis[nx][ny]) {
tmp = true;
}
}
return tmp;
};
int l = 0, r = n * n, ans;
while (l <= r) {
int mid = (l + r) / 2;
if (ok(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << "\n";
}
