#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const int maxn = 8e2 + 20;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
bool grass[maxn][maxn];
int dist_h[maxn][maxn];
int dist_m[maxn][maxn];
int n, k, sx, sy, ex, ey;
bool check() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != sx || j != sy) {
dist_m[i][j] = -1;
}
}
}
deque<pair<int, int>> q;
q.emplace_back(sx, sy);
while (!q.empty()) {
int cx = q.front().first;
int cy = q.front().second;
q.pop_front();
for (int d = 0; d < 4; d++) {
int nx = cx + dx[d];
int ny = cy + dy[d];
if (nx == ex && ny == ey) {
return true;
}
if (dist_m[nx][ny] == -1 && dist_m[cx][cy] + 1 < dist_h[nx][ny] * k) {
dist_m[nx][ny] = dist_m[cx][cy] + 1;
q.emplace_back(nx, ny);
}
}
}
return false;
}
void just_do_it() {
cin >> n >> k;
deque<pair<int, int>> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char c;
cin >> c;
if (c == 'G') {
grass[i][j] = true;
}
if (c == 'M') {
grass[i][j] = true;
sx = i;
sy = j;
}
if (c == 'D') {
ex = i;
ey = j;
}
if (c == 'H') {
dist_h[i][j] = 0;
q.emplace_back(i, j);
}
else {
dist_h[i][j] = -1;
}
}
}
while (!q.empty()) {
int cx = q.front().first;
int cy = q.front().second;
q.pop_front();
for (int d = 0; d < 4; d++) {
int nx = cx + dx[d];
int ny = cy + dy[d];
if (grass[nx][ny] && dist_h[nx][ny] == -1) {
dist_h[nx][ny] = dist_h[cx][cy] + 1;
q.emplace_back(nx, ny);
}
}
}
int res = -1;
int lt = 0;
int rt = dist_h[sx][sy] - 1;
while (lt <= rt) {
int mt = (lt + rt) / 2;
dist_m[sx][sy] = mt * k;
if (check()) {
res = mt;
lt = mt + 1;
}
else {
rt = mt - 1;
}
}
cout << res;
}
