#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define int long long
const int INF = 1e9;
const int MAXN = 805;
int n, s;
char grid[MAXN][MAXN];
int bee_time[MAXN][MAXN]; // time bees reach each cell
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
pii mecho, home;
bool in_bounds(int x, int y) {
return x >= 0 && y >= 0 && x < n && y < n;
}
void bfs_bees() {
queue<pii> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
bee_time[i][j] = INF;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 'H') {
bee_time[i][j] = 0;
q.push({i, j});
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (in_bounds(nx, ny) && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M' || grid[nx][ny] == 'D') && bee_time[nx][ny] == INF) {
bee_time[nx][ny] = bee_time[x][y] + 1;
q.push({nx, ny});
}
}
}
}
bool can_escape(int wait_time) {
queue<tuple<int, int, int>> q;
vector<vector<int>> visited(n, vector<int>(n, INF));
if (wait_time >= bee_time[mecho.first][mecho.second]) return false;
visited[mecho.first][mecho.second] = 0;
q.push({mecho.first, mecho.second, 0});
while (!q.empty()) {
auto [x, y, dist] = q.front(); q.pop();
int minute = (dist + s - 1) / s;
if (wait_time + minute >= bee_time[x][y]) continue;
if (x == home.first && y == home.second) return true;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (in_bounds(nx, ny) && (grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && visited[nx][ny] > dist + 1) {
visited[nx][ny] = dist + 1;
q.push({nx, ny, dist + 1});
}
}
}
return false;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
for (int i = 0; i < n; i++) {
cin >> grid[i];
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'M') mecho = {i, j};
if (grid[i][j] == 'D') home = {i, j};
}
}
bfs_bees();
int lo = 0, hi = n * n, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (can_escape(mid)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << ans+1 << '\n';
return 0;
}
