#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1007, INF = 1e9 + 7;
int n, S;
string a[N];
int bee_dist[N][N];
bool can_bee(int i, int j) {
return 0 <= i && i < n && 0 <= j && j < n && (a[i][j] == 'G' || a[i][j] == 'M' || a[i][j] == 'H');
}
vector <ii> v = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
void bfs1() {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
bee_dist[i][j] = INF;
}
}
queue <ii> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i][j] == 'H') {
bee_dist[i][j] = 0;
q.push(mp(i, j));
}
}
}
while (q.size()) {
auto p = q.front(); q.pop();
for (auto e : v) {
int x = p.f + e.f, y = p.s + e.s;
if (can_bee(x, y) && bee_dist[p.f][p.s] + 1 < bee_dist[x][y]) {
bee_dist[x][y] = bee_dist[p.f][p.s] + 1;
q.push(mp(x, y));
}
}
}
}
bool can_bear(int i, int j, int t, int m) {
t = t / S;
return 0 <= i && i < n && 0 <= j && j < n && (a[i][j] == 'G' || a[i][j] == 'M' || a[i][j] == 'D') && bee_dist[i][j] > t + m;
}
int sx, sy;
int dist[N][N];
bool can(int m) {
if (bee_dist[sx][sy] <= m)
return 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
dist[i][j] = INF;
}
}
queue <ii> q;
dist[sx][sy] = 0;
q.push(mp(sx, sy));
while (q.size()) {
auto p = q.front(); q.pop();
if (a[p.f][p.s] == 'D')
return 1;
for (auto e : v) {
int x = p.f + e.f, y = p.s + e.s;
if (can_bear(x, y, dist[p.f][p.s] + 1, m) && dist[p.f][p.s] + 1 < dist[x][y]) {
dist[x][y] = dist[p.f][p.s] + 1;
q.push(mp(x, y));
}
}
}
return 0;
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
#define endl '\n'
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> S;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i][j] == 'M') {
sx = i;
sy = j;
}
}
}
bfs1();
int l = -1, r = INF;
while (l < r - 1) {
int m = (l + r) >> 1;
if (can(m))
l = m;
else
r = m;
}
cout << l << endl;
}
