#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define pb push_back
#define size(a) (int) a.size()
#define all(a) a.begin(), a.end()
const int maxn = 800 + 4, inf = 1e8;
int n, s, mx, my, dx, dy, d[maxn][maxn], save[maxn][maxn];
bitset<maxn> vis[maxn];
string a[maxn];
queue<array<int, 2>> q;
void rest() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
vis[i][j] = 0;
d[i][j] = inf;
}
}
return;
}
bool check0(int x, int y, int dis) {
bool ret = (0 <= x && x < n);
ret &= (0 <= y && y < n);
if (ret) {
ret &= !vis[x][y];
ret &= (a[x][y] == 'G' || a[x][y] == 'M');
}
return ret;
}
void upd0(int x, int y) {
int dis = d[x][y] + 1;
if (check0(x - 1, y, dis)) {
vis[x - 1][y] = 1;
d[x - 1][y] = dis;
q.push({x - 1, y});
}
if (check0(x + 1, y, dis)) {
vis[x + 1][y] = 1;
d[x + 1][y] = dis;
q.push({x + 1, y});
}
if (check0(x, y - 1, dis)) {
vis[x][y - 1] = 1;
d[x][y - 1] = dis;
q.push({x, y - 1});
}
if (check0(x, y + 1, dis)) {
vis[x][y + 1] = 1;
d[x][y + 1] = dis;
q.push({x, y + 1});
}
}
bool check1(int x, int y, int dis, int k) {
bool ret = (0 <= x && x < n);
ret &= (0 <= y && y < n);
if (ret) {
ret &= !vis[x][y];
ret &= a[x][y] == 'G' || a[x][y] == 'D';
ret &= (dis + s - 1) / s <= save[x][y] - k;
}
return ret;
}
void upd1(int x, int y, int k) {
int dis = d[x][y] + 1;
if (check1(x - 1, y, dis, k)) {
vis[x - 1][y] = 1;
d[x - 1][y] = dis;
q.push({x - 1, y});
}
if (check1(x + 1, y, dis, k)) {
vis[x + 1][y] = 1;
d[x + 1][y] = dis;
q.push({x + 1, y});
}
if (check1(x, y - 1, dis, k)) {
vis[x][y - 1] = 1;
d[x][y - 1] = dis;
q.push({x, y - 1});
}
if (check1(x, y + 1, dis, k)) {
vis[x][y + 1] = 1;
d[x][y + 1] = dis;
q.push({x, y + 1});
}
}
bool bfs(int k) {
rest();
d[mx][my] = 0;
vis[mx][my] = 1;
q.push({mx, my});
while (!q.empty()) {
array<int, 2> v = q.front();
q.pop();
upd1(v[0], v[1], k);
}
return d[dx][dy] != inf;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> s;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
rest();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i][j] == 'H') {
q.push({i, j});
vis[i][j] = 1;
d[i][j] = 0;
}
}
}
while (!q.empty()) {
array<int, 2> v = q.front();
q.pop();
upd0(v[0], v[1]);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i][j] == 'M') {
mx = i;
my = j;
}
if (a[i][j] == 'D') {
dx = i;
dy = j;
}
save[i][j] = d[i][j];
}
}
int l, r;
l = -1;
r = save[mx][my];
while (r - l > 1) {
int m = (l + r) >> 1;
if (bfs(m)) {
l = m;
}
else {
r = m;
}
}
cout << l << '\n';
return 0;
}
