#include <bits/stdc++.h>
using namespace std;
vector<string> graph;
int n, s;
bool reached(int bear_time, int bee_time) {
return bear_time / s < bee_time;
}
bool valid(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n &&
(graph[x][y] == 'G' || graph[x][y] == 'M');
}
int main() {
pair<int, int> bear, home;
vector<pair<int, int>> hives;
cin >> n >> s;
graph.resize(n);
for (int i = 0; i < n; i++) {
cin >> graph[i];
for (int j = 0; j < n; j++) {
if (graph[i][j] == 'M') {
bear = {i, j};
} else if (graph[i][j] == 'H') {
hives.push_back({ i, j });
} else if (graph[i][j] == 'D') {
home = { i, j };
}
}
}
int l = 0, r = n * n; // n * n = 800 * 800 - so doable i think? N^2logN
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
while (l <= r) {
int eating_time = (l + r) / 2;
queue<pair<int, int>> q;
vector<vector<int>> bee_time(n, vector<int>(n));
vector<vector<int>> bear_time(n, vector<int>(n));
vector<vector<bool>> bear_visited(n, vector<bool>(n));
vector<vector<bool>> bee_visited(n, vector<bool>(n));
for (auto [x, y] : hives) {
q.push({ x, y });
bee_visited[x][y] = true;
}
while (!q.empty()) {
int x = q.front().first;
int 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) && !bee_visited[nx][ny]) {
q.push({ nx, ny});
bee_visited[nx][ny] = true;
bee_time[nx][ny] = bee_time[x][y] + 1;
}
}
}
q.push({ bear.first, bear.second });
bear_visited[bear.first][bear.second] = true;
if (bee_time[bear.first][bear.second] <= eating_time) {
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) && !bear_visited[nx][ny]
&& reached(bear_time[x][y] + 1, bee_time[nx][ny] - eating_time)) {
bear_time[nx][ny] = bear_time[x][y] + 1;
q.push({ nx, ny});
bear_visited[nx][ny] = true;
}
}
}
bool reachable = false;
for (int i = 0; i < 4; i++) {
int x = dx[i] + home.first, y = dy[i] + home.second;
if (valid(x, y) && bear_visited[x][y]
&& reached(bear_time[x][y], bee_time[x][y] - eating_time)) {
reachable = true;
}
}
if (reachable) {
l = eating_time + 1;
} else {
r = eating_time - 1;
}
}
cout << l - 1 << endl;
}
