#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, s; cin >> n >> s;
vector<string> grid(n);
for (int i = 0; i < n; i++) cin >> grid[i];
vector<vector<int>> bee_time(n, vector<int>(n, -1));
int homex = 0, homey = 0;
int hpx = 0, hpy = 0;
queue<pair<int,int>> qb;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'H') {
qb.push({i, j});
bee_time[i][j] = 0;
} else if (grid[i][j] == 'D') {
// Home
homex = i; homey = j;
} else if (grid[i][j] == 'M') {
hpx = i; hpy = j;
}
}
}
while (!qb.empty()) {
int x = qb.front().first, y = qb.front().second;
qb.pop();
for (int i = 0; i < 4; i++) {
int nx = dx[i] + x, ny = dy[i] + y;
if (nx >= 0 && nx < n && ny >= 0 && ny < n && bee_time[nx][ny] == -1 && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M')) {
bee_time[nx][ny] = bee_time[x][y] + 1;
qb.push({nx, ny});
}
}
}
// BSTA
int l = 0, r = 2000;
int ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
// Run a BFS, see if you can reach home from D
vector<vector<int>> dist(n, vector<int>(n, -1));
dist[hpx][hpy] = 0;
int valid = 0;
queue<pair<int, int>> q;
q.push({hpx, hpy});
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
if (x == homex && y == homey) {
valid = 1;
break;
}
for (int i = 0; i < 4; i++) {
int nx = dx[i] + x, ny = dy[i] + y;
if (nx >= 0 && nx < n && ny >= 0 && ny < n && (grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && dist[nx][ny] == -1) {
int total_dist = mid + ((dist[x][y] + s) / s);
if (total_dist < bee_time[nx][ny] || bee_time[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
}
if (valid) {
ans = mid + 1;
l = mid + 1;
} else r = mid - 1;
}
cout << ans << '\n';
return 0;
}
