#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n, s;
cin >> n>> s;
vector<vector<char> > grid(n, vector<char>(n));
queue<pair<ll ,ll> > q1;
queue<pair<ll ,ll> > q2;
pair<ll ,ll> home;
pair<ll ,ll> start;
vector<vector<ll> > hdist(n, vector<ll>(n, -1));
vector<vector<ll> > mdist(n, vector<ll>(n, -1));
for (ll i = 0; i < n; i++) for (ll j = 0; j < n; j++) {
cin >> grid[i][j];
if (grid[i][j] == 'H') {
q1.push({i, j});
hdist[i][j] = 0;
}
else if (grid[i][j] == 'M') {
q2.push({i, j});
mdist[i][j] = 0;
start = {i, j};
}
else if (grid[i][j] == 'D') home = {i, j};
}
vector<ll> dx = {1, -1, 0, 0};
vector<ll> dy = {0, 0, -1, 1};
while (!q1.empty() && hdist[home.first][home.second] == -1) {
pair<ll, ll> curr = q1.front();
q1.pop();
for (ll i = 0; i < 4; i++) {
ll x = curr.first + dx[i];
ll y = curr.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n) {
if (hdist[x][y] == -1 && grid[x][y] == 'G') {
hdist[x][y] = hdist[curr.first][curr.second] + s;
q1.push({x, y});
}
}
}
}
vector<vector<pair<ll, ll> > > parent(n, vector<pair<ll, ll> >(n, {-1, -1}));
while (!q2.empty() && mdist[home.first][home.second] == -1) {
pair<ll, ll> curr = q2.front();
q2.pop();
for (ll i = 0; i < 4; i++) {
ll x = curr.first + dx[i];
ll y = curr.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < n) {
if (mdist[x][y] == -1 && (grid[x][y] == 'G' || grid[x][y] == 'D') && (hdist[x][y] > mdist[curr.first][curr.second] + 1 || hdist[x][y ] == -1)) {
mdist[x][y] = mdist[curr.first][curr.second] + 1;
q2.push({x, y});
parent[x][y] = {curr.first, curr.second};
}
}
}
}
ll ans = 100000000;
pair<ll ,ll> current = home;
// cout << mdist[home.first][home.second] << endl;
if (mdist[home.first][home.second] == -1) {
cout << -1 << endl;
return 0;
}
while (current != start) {
ll x = current.first;
ll y = current.second;
if (hdist[x][y] != -1) {
// cout << x << y << hdist[x][y] << endl;
ans = min(ans, hdist[x][y]-mdist[x][y]);
}
current = parent[x][y];
}
// for (ll i = 0; i < 4; i++) {
// ll x = home.first + dx[i];
// ll y = home.second + dy[i];
// if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] != 'T') {
// ans = max(hdist[x][y] - mdist[x][y], ans);
// cout << mdist[x][y] << hdist[x][y] << x << y << endl;
// }
// }
cout << ans/s << endl;
}
