#include <bits/stdc++.h>
using namespace std;
const vector<int> dx = {0, 0, -1, 1};
const vector<int> dy = {1, -1, 0, 0};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, s;
cin >> n >> s;
vector<string> grid(n);
queue< pair<int, int> > q1, q2;
vector< vector<int> > dist1(n, vector<int>(n, -1)), dist2(n, vector<int>(n, -1));
int mr, mc, dr, dc;
for (int i = 0; i < n; i++) {
cin >> grid[i];
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'M') {
q1.push({i, j});
dist1[i][j] = 0;
mr = i; mc = j;
} else if (grid[i][j] == 'H') {
q2.push({i, j});
dist2[i][j] = 0;
} else if (grid[i][j] == 'D') {
dr = i; dc = j;
}
}
}
while (!q1.empty()) {
int r = q1.front().first, c = q1.front().second;
q1.pop();
for (int k = 0; k < 4; k++) {
int nr = r + dx[k], nc = c + dy[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || dist1[nr][nc] != -1) {
continue;
}
dist1[nr][nc] = dist1[r][c] + 1;
q1.push({nr, nc});
}
}
while (!q2.empty()) {
int r = q2.front().first, c = q2.front().second;
q2.pop();
for (int k = 0; k < 4; k++) {
int nr = r + dx[k], nc = c + dy[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || dist2[nr][nc] != -1) {
continue;
}
dist2[nr][nc] = dist2[r][c] + s;
q2.push({nr, nc});
}
}
int lo = 0, hi = n * n, ans = -1;
for (int i = 0; i < 50; i++) {
int mid = (lo + hi + 1) / 2;
vector< vector<bool> > was(n, vector<bool>(n, false));
queue< pair<int, int> > q;
q.push({mr, mc});
while (!q.empty()) {
int r = q.front().first, c = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nr = r + dx[k], nc = c + dy[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || dist1[nr][nc] + 4 * mid > dist2[nr][nc] || was[nr][nc]) {
continue;
}
was[nr][nc] = true;
q.push({nr, nc});
}
}
if (was[dr][dc]) {
lo = mid;
ans = mid;
} else {
hi = mid - 1;
}
}
cout << ans << '\n';
return 0;
}
