#include <bits/stdc++.h>
using namespace std;
using lli = long long;
/*How to use:
Tvector <int, 2> g(n); //graph
Tvector <int, 3> f(n, k, 2) = f[n][k][2]
*/
template <class Tp, int D = 1>
struct Tvector : public vector<Tvector<Tp, D - 1>> {
template <class... Args>
Tvector(int n = 0, Args... args) : vector<Tvector<Tp, D - 1>>(n, Tvector<Tp, D - 1>(args...)) {}
};
template <class Tp>
struct Tvector<Tp, 1> : public vector<Tp> {
Tvector(int n = 0, Tp val = Tp()) : vector<Tp>(n, val) {}
};
#ifdef LOCAL
#include </home/marcus06/CP/Library/debug.h>
#else
#define debug(...)
#endif
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
void solve() {
int n, s;
cin >> n >> s;
Tvector <char, 2> g(n, n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> g[i][j];
}
}
int h_x, h_y;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == 'D') {
h_x = i;
h_y = j;
}
}
}
int m_x, m_y;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == 'M') {
m_x = i;
m_y = j;
}
}
}
auto valid = [&](int x, int y) -> bool {
return (x >= 0 && y >= 0 && x < n && y < n && (g[x][y] == 'G' || g[x][y] == 'M'));
};
Tvector <int, 2> bee_dist(n, n, -1);
{
queue <pair <int, int>> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == 'H') {
bee_dist[i][j] = 0;
q.emplace(i, j);
}
}
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int u = x + dx[i], v = y + dy[i];
if (valid(u, v) && bee_dist[u][v] == -1) {
bee_dist[u][v] = bee_dist[x][y] + 1;
q.emplace(u, v);
}
}
}
}
Tvector <int, 2> Mecho_dist(n, n);
auto possible = [&](int t) -> bool {
queue <pair <int, int>> q;
fill(Mecho_dist.begin(), Mecho_dist.end(), Tvector <int, 1> (n, -1));
q.emplace(m_x, m_y);
Mecho_dist[m_x][m_y] = 0;
if (bee_dist[m_x][m_y] <= t) q.pop();
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int u = x + dx[i], v = y + dy[i];
if (valid(u, v) && Mecho_dist[u][v] == -1) {
int nxt_dist = t + (Mecho_dist[x][y] + 1) / s;
if (nxt_dist < bee_dist[u][v]) {
Mecho_dist[u][v] = Mecho_dist[x][y] + 1;
q.emplace(u, v);
}
}
}
}
bool is_success = false;
for (int i = 0; i < 4; ++i) {
int u = h_x + dx[i], v = h_y + dy[i];
if (valid(u, v) && Mecho_dist[u][v] != -1) {
if (t + Mecho_dist[u][v] / s < bee_dist[u][v]) is_success = true;
}
}
return is_success;
};
int l = -1, r = int(1e9);
while (r - l > 1) {
int mid = (l + r) / 2;
if (possible(mid))
l = mid;
else
r = mid;
}
cout << l << '\n';
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
auto begin = std::chrono::high_resolution_clock::now();
#endif
int tt = 1;
while (tt--) {
solve();
}
#ifdef LOCAL
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
#endif
return 0;
}
