#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
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> > q;
vector< vector<int> > dist1(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') {
mr = i; mc = j;
} else if (grid[i][j] == 'H') {
q.push({i, j});
dist1[i][j] = 0;
} else if (grid[i][j] == 'D') {
dr = i; dc = j;
}
}
}
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] != -1 || grid[nr][nc] == 'D') {
continue;
}
dist1[nr][nc] = dist1[r][c] + s;
q.push({nr, nc});
}
}
int lo = 0, hi = n * n, ans = -1;
for (int i = 0; i < 50; i++) {
int mid = (lo + hi) / 2;
//cout << mid << endl;
vector< vector<int> > dist2(n, vector<int>(n, INF));
dist2[mr][mc] = s * mid;
if (dist2[mr][mc] >= dist1[mr][mc]) {
hi = mid - 1;
continue;
}
q.push({mr, mc});
while (!q.empty()) {
int r = q.front().first, c = q.front().second;
//cout << r << ' ' << c << endl;
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 || dist2[r][c] + 1 >= dist2[nr][nc] || ((nr != dr || nc != dc) && dist2[r][c] + 1 >= dist1[nr][nc]) || grid[nr][nc] == 'T') {
continue;
}
dist2[nr][nc] = dist2[r][c] + 1;
q.push({nr, nc});
}
}
if (dist2[dr][dc] < INF) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << ans << '\n';
return 0;
}
