#include <bits/stdc++.h>
using namespace std;
const int N = 805;
const int dI[4] = {-1, 0, +1, 0};
const int dJ[4] = {0, +1, 0, -1};
int n, s;
char a[N][N];
long long d[N][N];
int f[N][N];
bool can[N][N];
int mx, my, dx, dy;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
memset(d, 0x3f, sizeof(d));
memset(f, 0x3f, sizeof(f));
queue<pair<int, int>> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == 'H') {
d[i][j] = 0;
q.push({i, j});
} else if (a[i][j] == 'M') {
mx = i;
my = j;
} else if (a[i][j] == 'D') {
dx = i;
dy = j;
}
}
}
while (!q.empty()) {
int x, y;
tie(x, y) = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = x + dI[dir];
int ny = y + dJ[dir];
if (1 <= nx && nx <= n && 1 <= ny && ny <= n && a[nx][ny] != 'D' && a[nx][ny] != 'T' && d[nx][ny] > d[x][y] + 1) {
d[nx][ny] = d[x][y] + 1;
q.push({nx, ny});
}
}
}
int l = 0, r = n * n, ans = -1;
while (l <= r) {
int m = (l + r) >> 1;
memset(f, 0x3f, sizeof(f));
memset(can, false, sizeof(can));
queue<pair<int, int>> q;
if (m < d[mx][my]) {
f[mx][my] = 0;
can[mx][my] = true;
q.push({mx, my});
}
while (!q.empty()) {
int x, y;
tie(x, y) = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = x + dI[dir];
int ny = y + dJ[dir];
if (1 <= nx && nx <= n && 1 <= ny && ny <= n && a[nx][ny] != 'T' && f[nx][ny] > f[x][y] + 1 && (f[x][y] + 1) / s + m < d[nx][ny] && !can[nx][ny]) {
f[nx][ny] = f[x][y] + 1;
can[nx][ny] = true;
q.push({nx, ny});
}
}
}
if (can[dx][dy]) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
cout << ans;
return 0;
}
