#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9+69;
const int MAXN = 800;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
vector<string> G(MAXN);
vector<vector<int>> G2(MAXN, vector<int>(MAXN,INF));
vector<vector<int>> G3(MAXN, vector<int>(MAXN,INF));
int n;
int s;
int sx, sy, ex, ey;
bool possible(int wait) {
queue <tuple<int,int,int>> q;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
G3[i][j] = -1;
}
}
if (wait * s >= G2[sx][sy]) {
//cout << "BRUH" << endl;
return false;
}
q.push({wait*s, sx, sy});
while (!q.empty()) {
int w = get<0>(q.front());
int x = get<1>(q.front());
int y = get<2>(q.front());
//if (G[x][y] == 'D') {
//cout << "YEH"<< endl;
//}
q.pop();
if (G3[x][y] != -1) continue;
G3[x][y] = w;
for (int i = 0; i < 4 ;++i) {
if (x + dx[i] < 0
|| x + dx[i] >= n
|| y + dy[i] < 0
|| y + dy[i] >= n
|| (G[x+dx[i]][y+dy[i]] == 'T')
|| w+1 >= G2[x+dx[i]][y+dy[i]] ) {
if (G[x+dx[i]][y+dy[i]] == 'D')
q.push({w+1, x+dx[i], y+dy[i]});
continue;
}
q.push({w+1, x+dx[i], y+dy[i]});
}
}
//cout << endl;
//cout << wait << endl;
//for (int i = 0; i < n; ++i) {
//for (int j = 0; j < n; ++j) {
//cout << G3[i][j] << " ";
//}
//cout << endl;
//}
return G3[ex][ey] != -1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cin >> s;
for (int i = 0; i < n; ++i) {
cin >> G[i];
}
queue<tuple<int,int,int>> q;
for (int i = 0; i < n; ++i) {
for (int j =0; j < n; ++j) {
if (G[i][j] == 'H') {
//G2[i][j] = 0;
G2[i][j] = -1;
q.push({0, i,j});
} else {
G2[i][j] = -1;
}
if (G[i][j] == 'M') {
sx = i;
sy = j;
}
if (G[i][j] == 'D') {
ex = i;
ey = j;
}
}
}
while(!q.empty()) {
int w = get<0>(q.front());
int x = get<1>(q.front());
int y = get<2>(q.front());
q.pop();
if (G2[x][y] != -1) continue;
G2[x][y] = w;
for (int i = 0; i < 4; ++i) {
if (x + dx[i] < 0
|| x + dx[i] >= n
|| y + dy[i] < 0
|| y + dy[i] >= n
|| (G[x+dx[i]][y+dy[i]] != 'G' && G[x+dx[i]][y+dy[i]] != 'M')) {
continue;
}
q.push({w+s, x+dx[i], y+dy[i]});
}
}
//for (int i = 0; i < n; ++i) {
//for (int j =0; j < n; ++j) {
//cout << G2[i][j] << " ";
//}
//cout << endl;
//}
if (!possible(0)) {
cout << "-1\n";
return 0;
}
int l = 0, h = MAXN * MAXN, m;
while(l < h) {
m = (l + h) / 2 + 1;
if (possible(m)) {
l = m;
} else {
h = m - 1;
}
}
cout << l << "\n";
return 0;
}
