#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
#define fast_io ios::sync_with_stdio(0), cin.tie(0)
#define pb push_back
template <typename T> using vt = vector<T>;
using vi = vt<int>;
using vs = vt<string>;
const int inf = 0x3f3f3f3f;
int main() {
fast_io;
int N, n, d; cin >> N >> d, n = N*N;
vs s(N); int srt, fin; vi hiv;
for(int i = 0; i < N; i++) {
cin >> s[i];
for(int j = 0; j < N; j++) {
int x = i*N+j;
if(s[i][j] == 'M') srt = x;
if(s[i][j] == 'D') fin = x;
if(s[i][j] == 'H') hiv.pb(x);
}
}
queue<int> q; vi hdis(n, inf), dis; int f;
auto put = [&] (int x, int y, int c) {
if(c == 0) {
if(hdis[y] < inf) return;
int a = y/N, b = y-a*N;
if(s[a][b] == 'T' || s[a][b] == 'D') return;
q.push(y), hdis[y] = hdis[x]+1;
} else
if(c == 1) {
if(dis[y] < inf) return;
if(y == fin) {
q.push(y), dis[y] = 0;
return;
}
int a = y/N, b = y-a*N;
if(s[a][b] == 'T') return;
int tim = f+(dis[x]+1)/d;
if(hdis[y] <= tim) return;
q.push(y), dis[y] = dis[x]+1;
}
};
auto bfs = [&] (int c) {
while(!q.empty()) {
int x = q.front(); q.pop();
if(x == fin) {
while(!q.empty()) q.pop();
return;
}
if(x%N > 0) put(x, x-1, c);
if(x%N<N-1) put(x, x+1, c);
if(x/N > 0) put(x, x-N, c);
if(x/N<N-1) put(x, x+N, c);
}
};
for(int x: hiv) q.push(x), hdis[x] = 0;
bfs(0);
auto poss = [&] (int m) {
if(m >= hdis[srt]) return 0;
q.push(srt), dis = vi(n, inf), dis[srt] = 0, f = m;
bfs(1);
return dis[fin] < inf? 1: 0;
};
int l = -1, r = inf, m;
while(l < r) {
m = l+r+1 >> 1;
if(poss(m)) l = m; else
r = m-1;
}
cout << l << "\n";
}
