#include <bits/stdc++.h>
// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = [] {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
int n, s;
pair<int, int> start, eend;
bool walls[800][800];
bool been[800][800];
long long dist[800][800];
bool check(long long t) {
queue<pair<long long, pair<int, int>>> q;
q.push({t, start});
while (q.size()) {
auto [d, p] = q.front();
auto [i, j] = p;
q.pop();
if (d >= dist[i][j]) continue;
if (eend.f == i && eend.s == j) return true;
if (0 < i && !been[i - 1][j]) {
been[i - 1][j] = true;
q.push({d + 1, {i - 1, j}});
}
if (0 < j && !been[i][j - 1]) {
been[i][j - 1] = true;
q.push({d + 1, {i, j - 1}});
}
if (i < n - 1 && !been[i + 1][j]) {
been[i + 1][j] = true;
q.push({d + 1, {i + 1, j}});
}
if (j < n - 1 && !been[i][j + 1]) {
been[i][j + 1] = true;
q.push({d + 1, {i, j + 1}});
}
}
return false;
}
int main() {
cin >> n >> s;
{
queue<pair<long long, pair<int, int>>> q;
fo(i, 0, n) {
string a;
cin >> a;
fo(j, 0, n) {
walls[i][j] = been[i][j] = a[j] != 'G' && a[j] != 'M';
if (a[j] == 'H') q.push({0, {i, j}});
if (a[j] == 'M') start = {i, j};
if (a[j] == 'D') eend = {i, j};
}
}
while (q.size()) {
auto [d, p] = q.front();
auto [i, j] = p;
q.pop();
if (0 < i && !been[i - 1][j]) {
been[i - 1][j] = true;
dist[i - 1][j] = d + s;
q.push({d + s, {i - 1, j}});
}
if (0 < j && !been[i][j - 1]) {
been[i][j - 1] = true;
dist[i][j - 1] = d + s;
q.push({d + s, {i, j - 1}});
}
if (i < n - 1 && !been[i + 1][j]) {
been[i + 1][j] = true;
dist[i + 1][j] = d + s;
q.push({d + s, {i + 1, j}});
}
if (j < n - 1 && !been[i][j + 1]) {
been[i][j + 1] = true;
dist[i][j + 1] = d + s;
q.push({d + s, {i, j + 1}});
}
}
}
dist[eend.f][eend.s] = 1000000000000000000;
walls[eend.f][eend.s] = false;
long long l = 0, r = 1000000000000000000;
while (l < r) {
long long mid = (l + r + 1) / 2;
fo(i, 0, n) fo(j, 0, n) been[i][j] = walls[i][j];
if (check(mid)) {
l = mid;
cerr << mid << endl;
} else r = mid - 1;
}
fo(i, 0, n) fo(j, 0, n) been[i][j] = walls[i][j];
if (check(l)) cout << l / s;
else cout << -1;
}
