#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 801;
int n, s;
vector<string> field(mxN);
int d1[mxN][mxN], d2[mxN][mxN];
bool vis1[mxN][mxN], vis2[mxN][mxN];
vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
void restart() {
memset(vis1, false, sizeof vis1);
memset(vis2, false, sizeof vis2);
memset(d1, 0, sizeof d1);
memset(d2, 0, sizeof d2);
}
bool valid(int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < n && (field[x][y] == 'G' ||
field[x][y] == 'M'));
}
bool reached(int a, int b) {
return a/s < b;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
array<int, 2> start, finish;
vector<array<int, 2>> hives;
for(int i = 0; i < n; i++) {
cin >> field[i];
for(int j = 0; j < n; j++) {
if(field[i][j] == 'M') start = {i, j};
else if(field[i][j] == 'H') hives.push_back({i, j});
else if(field[i][j] == 'D') finish = {i, j};
}
}
int l = 0, r = n * n;
bool imp = true;
while(l <= r) {
int mid = (r+l) / 2;
restart();
queue<array<int, 2>> q;
for(auto it : hives) {
q.push(it);
vis1[it[0]][it[1]] = true;
}
while(!q.empty()) {
int x = q.front()[0], y = q.front()[1];
q.pop();
for(int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if(valid(a, b) && !vis1[a][b]) {
vis1[a][b] = true;
d1[a][b] = d1[x][y]+1;
q.push({a, b});
}
}
}
q.push(start);
vis2[start[0]][start[1]] = true;
if(d1[start[0]][start[1]] <= mid) q.pop();
while(!q.empty()) {
int x = q.front()[0], y = q.front()[1];
q.pop();
for(int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if(valid(a, b) && !vis2[a][b] && reached(d2[x][y]+1,
d1[a][b]-mid)) {
vis2[a][b] = true;
q.push({a, b});
d2[a][b] = d2[x][y]+1;
}
}
}
bool can = false;
for(int k = 0; k < 4; k++) {
int a = finish[0]+dx[k], b = finish[1]+dy[k];
if(valid(a, b) && reached(d2[a][b], d1[a][b]-mid) && vis2[a][b]) {
can = true;
}
}
if(can)
l = mid+1;
else
r = mid-1;
}
cout << l-1;
}
