#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};
const int MAX = 800;
int n, S;
int xM, yM;
int xD, yD;
char a[MAX][MAX];
int bee[MAX][MAX];
int bear[MAX][MAX];
queue<pair<int, int>> q;
bool ok(int add) {
if (bee[xM][yM] <= add) return false;
memset(bear, -1, sizeof bear);
q.push({xM, yM});
bear[xM][yM] = 0;
while (q.size()) {
int u = q.front().fi;
int v = q.front().se;
q.pop();
for (int i = 0; i < 4; ++i) {
int x = u + dx[i], y = v + dy[i];
if (x < 0 || x >= n) continue;
if (y < 0 || y >= n) continue;
if (a[x][y] == 'M' || a[x][y] == 'G') {
int candidate = bear[u][v] + 1;
if (candidate / S < bee[x][y] - add) {
if (bear[x][y] == -1) {
q.push({x, y});
bear[x][y] = candidate;
}
}
}
}
}
for (int i = 0; i < 4; ++i) {
int x = xD + dx[i], y = yD + dy[i];
if (x < 0 || x >= n) continue;
if (y < 0 || y >= n) continue;
if (bear[x][y] == -1) continue;
if (a[x][y] == 'G' || a[x][y] == 'M') {
if (bear[x][y] / S < bee[x][y] - add) return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> S;
memset(bee, -1, sizeof bee);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> a[i][j];
if (a[i][j] == 'H') {
bee[i][j] = 0;
q.push({i, j});
}
if (a[i][j] == 'D') {
xD = i, yD = j;
}
if (a[i][j] == 'M') {
xM = i, yM = j;
}
}
}
//
while (q.size()) {
int u = q.front().fi;
int v = q.front().se;
q.pop();
for (int i = 0; i < 4; ++i) {
int x = u + dx[i], y = v + dy[i];
if (x < 0 || x >= n) continue;
if (y < 0 || y >= n) continue;
if (a[x][y] == 'G' || a[x][y] == 'M') {
if (bee[x][y] == -1) {
q.push({x, y});
bee[x][y] = bee[u][v] + 1;
}
}
}
}
//
int l = 0;
int r = n * n;
while (l <= r) {
int mid = l + r >> 1;
if (ok(mid)) l = mid + 1;
else r = mid - 1;
}
cout << l - 1;
return 0;
}
