#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
int N, S;
const int MAXN=801;
char frst[MAXN][MAXN];
int hive[MAXN][MAXN], dest[MAXN][MAXN];
int dir[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
inline bool valid_loc(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
int main() {
cin >> N >> S;
pair<int, int> mloc, dloc;
memset(hive, -1, sizeof(hive));
queue<pair<int, int>> bees;
for (int i = 0; i < N; ++i) {
cin >> frst[i];
for (int j = 0; j < N; ++j) {
if (frst[i][j] == 'H') {
hive[i][j] = 0;
bees.push({i, j});
} else if (frst[i][j] == 'M') {
mloc = {i, j};
} else if (frst[i][j] == 'D') {
dloc = {i, j};
}
}
}
while (!bees.empty()) {
auto bee = bees.front();
bees.pop();
for (int k = 0; k < 4; ++k) {
int x = bee.first + dir[k][0], y = bee.second + dir[k][1];
if (valid_loc(x, y) && hive[x][y] == -1 && (frst[x][y] == 'G' || frst[x][y] == 'M')) {
hive[x][y] = hive[bee.first][bee.second] + 1;
bees.push({x, y});
}
}
}
memset(dest, -1, sizeof(dest));
priority_queue<pair<pair<int, int>, pair<int, int>>> bears;
dest[dloc.first][dloc.second] = 1000000;
bears.push({{1000000, 1}, {dloc.first, dloc.second}});
while (!bears.empty()) {
auto bear = bears.top().second;
auto step = bears.top().first.second;
bears.pop();
// cerr << bear.first << "," << bear.second << " " << dest[bear.first][bear.second] << ":" << step << endl;
for (int k = 0; k < 4; ++k) {
int x = bear.first + dir[k][0], y = bear.second + dir[k][1];
if (valid_loc(x, y) && dest[x][y] == -1 && (frst[x][y] == 'G' || frst[x][y] == 'M')) {
int ss = step;
int dd = dest[bear.first][bear.second];
if (ss == 1) {
ss = S;
dd -= 1;
} else {
ss -= 1;
}
if (dd < 0) {
continue;
}
if (hive[x][y] <= 0) {
continue;
}
if (hive[x][y] <= dd) {
dd = hive[x][y] - 1;
ss = S;
}
dest[x][y] = dd;
bears.push({{dd, ss}, {x, y}});
}
}
}
cout << dest[mloc.first][mloc.second] << endl;
return 0;
}
