#include<bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
#define CASES 0
int N, S;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
const int MAXN = 800;
string grid[MAXN];
pii start, finish;
int wall[MAXN][MAXN];
int bee[MAXN][MAXN];
inline bool inBounds(const int r, const int c) {
return 0 <= r and r < N and 0 <= c and c < N and !wall[r][c];
}
void solve(int tc) {
cin >> N >> S;
rep(i,0,N) cin >> grid[i];
rep(i,0,N) rep(j,0,N) bee[i][j] = INT_MAX;
queue<pii> bq;
rep(i,0,N) rep(j,0,N) switch(grid[i][j]) {
case 'T':
wall[i][j] = 1;
break;
case 'M':
start = {i, j};
break;
case 'D':
wall[i][j] = 1;
finish = {i, j};
break;
case 'H':
bee[i][j] = 0;
bq.emplace(i, j);
break;
}
// bee-FS
while(sz(bq)) {
int r, c, rr, cc;
tie(r, c) = bq.front(); bq.pop();
rep(d,0,4) if(inBounds(rr = r + dr[d], cc = c+dc[d]))
if(bee[r][c] + S < bee[rr][cc])
bee[rr][cc] = bee[r][c] + S,
bq.emplace(rr, cc);
}
wall[finish.first][finish.second] = 0;
auto test = [&](int delay) {
vvi dist(N, vi(N, INT_MAX));
queue<pii> mq; mq.push(start);
dist[start.first][start.second] = delay * S;
if(delay * S >= bee[start.first][start.second]) return false;
while(sz(mq)) {
if(mq.front() == finish) return true;
int r, c, rr, cc;
tie(r, c) = mq.front(); mq.pop();
rep(d,0,4) if(inBounds(rr = r + dr[d], cc = c+dc[d]))
if(dist[r][c]+1 < dist[rr][cc] and dist[r][c]+1 < bee[rr][cc])
dist[rr][cc] = dist[r][c] + 1,
mq.emplace(rr, cc);
}
return false;
};
int res = -1;
for(int x = 1 << 21; x; x >>= 1)
if(test(res+x)) res += x;
cout << res << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int T = 1, t = 0; if(CASES) cin >> T;
while(t++ < T) solve(t);
return 0;
}
