#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, s;
vector<string> forest;
vector<vector<int>> beeDist;
int xStart, yStart, xEnd, yEnd;
vector<int> dirx = {1, 0, -1, 0}, diry = {0, 1, 0, -1};
vector<vector<int>> mechoTime;
bool mecho(int wait) {
if(wait>=beeDist[xStart][yStart]) {
return false;
}
queue<pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mechoTime[i][j] = INT_MAX;
}
}
mechoTime[xStart][yStart] = 0;
q.push({xStart, yStart});
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nextX = x + dirx[i], nextY = y + diry[i];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n &&
mechoTime[nextX][nextY] > mechoTime[x][y] + 1 &&
forest[nextX][nextY] != 'T' && forest[nextX][nextY]!='D' &&
beeDist[nextX][nextY] * s > (mechoTime[x][y] + 1) + wait * s) {
mechoTime[nextX][nextY] = mechoTime[x][y] + 1;
q.push({nextX, nextY});
}
}
}
for (int i = 0; i < 4; i++) {
int nextX = xEnd + dirx[i], nextY = yEnd + diry[i];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n &&
mechoTime[nextX][nextY] != INT_MAX) {
return true;
}
}
return false;
}
int main() {
cin >> n >> s;
forest.resize(n);
for (int i = 0; i < n; i++) {
cin >> forest[i];
}
queue<pair<int, int>> q;
beeDist.resize(n, vector<int>(n, INT_MAX));
mechoTime.resize(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (forest[i][j] == 'H') {
q.push({i, j});
beeDist[i][j] = 0;
} else if (forest[i][j] == 'M') {
xStart = i;
yStart = j;
} else if (forest[i][j] == 'D') {
xEnd = i;
yEnd = j;
}
}
}
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nextX = x + dirx[i], nextY = y + diry[i];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n &&
forest[nextX][nextY] != 'T' && forest[nextX][nextY] != 'D' &&
beeDist[nextX][nextY] > beeDist[x][y] + 1) {
beeDist[nextX][nextY] = beeDist[x][y] + 1;
q.push({nextX, nextY});
}
}
}
int l = 0, r = n * n;
while (l <= r) {
int m = (r - l) / 2 + l;
if (mecho(m)) {
l = m + 1;
} else {
r = m - 1;
}
}
cout << r << endl;
}
