#include <bits/stdc++.h>
using namespace std;
const int NN = 2000 + 4, DX[4] = {1, -1, 0, 0}, DY[4] = {0, 0, 1, -1};
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
char G[NN][NN];
int N, S, B[NN][NN];
bool Vis[NN][NN];
struct Point {
int x, y;
};
bool check(const Point& st, int delay) {
if (delay * S >= B[st.x][st.y]) return false;
memset(Vis, 0, sizeof(Vis));
queue<pair<int, Point> > Q;
Q.push({delay * S, st}), Vis[st.x][st.y] = true;
while (!Q.empty()) {
auto p = Q.front();
Q.pop();
int d = p.first, x = p.second.x, y = p.second.y;
if (G[x][y] == 'D') return true;
_for(i, 0, 4) {
int nx = x + DX[i], ny = y + DY[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= N || G[nx][ny] == 'T' ||
(d + 1) >= B[nx][ny] || Vis[nx][ny])
continue;
Q.push({d + 1, {nx, ny}}), Vis[nx][ny] = true;
}
}
return false;
}
int main() {
cin >> N >> S;
queue<Point> Q;
Point Honey, Home;
memset(B, -1, sizeof(B));
_for(i, 0, N) {
cin >> ws;
_for(j, 0, N) {
char& c = G[i][j];
cin >> c;
if (c == 'H') Q.push({i, j}), B[i][j] = 0;
if (c == 'M') Honey = {i, j}, c = 'G';
if (c == 'D') Home = {i, j};
}
}
while (!Q.empty()) {
Point p = Q.front();
Q.pop();
_for(i, 0, 4) {
Point np{p.x + DX[i], p.y + DY[i]};
if (np.x < 0 || np.x >= N || np.y < 0 || np.y >= N ||
G[np.x][np.y] != 'G' || B[np.x][np.y] != -1)
continue;
B[np.x][np.y] = B[p.x][p.y] + S, Q.push({np.x, np.y});
}
}
B[Home.x][Home.y] = N * N * S;
int L = -1, R = 2 * N * N;
while (L + 1 < R) {
int mid = (L + R) / 2;
(check(Honey, mid) ? L : R) = mid;
}
cout << L << endl;
return 0;
}
