#include <bits/stdc++.h>
using namespace std;
const int N = 800;
const int INF = 1e9+69;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, S;
string mat[N];
int beeDist[N][N], d[N][N];
bool vis[N][N];
int Mx, My, Dx, Dy;
queue< pair<int,int> > Q;
bool call(int T) {
if(T * S >= beeDist[Mx][My]) return false;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
vis[i][j] = false;
vis[Mx][My] = true; d[Mx][My] = T * S;
Q.push(make_pair(Mx,My));
while(!Q.empty()) {
auto it = Q.front(); Q.pop();
int ux = it.first, uy = it.second;
for(int k = 0; k < 4; k++) {
int tx = ux + dx[k], ty = uy + dy[k];
if(min(tx,ty) < 0 || max(tx,ty) >= n || mat[tx][ty] == 'T' || mat[tx][ty] == 'H' || vis[tx][ty] || d[ux][uy] + 1 >= beeDist[tx][ty]) continue;
vis[tx][ty] = 1; d[tx][ty] = d[ux][uy] + 1; Q.push(make_pair(tx,ty));
}
} return vis[Dx][Dy];
}
int main() {
cin >> n >> S;
for(int i = 0; i < n; i++) cin >> mat[i];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
beeDist[i][j] = INF;
if(mat[i][j] == 'M') Mx = i, My = j;
else if(mat[i][j] == 'D') Dx = i, Dy = j;
else if(mat[i][j] == 'H') {
Q.push(make_pair(i,j));
beeDist[i][j] = 0;
}
}
}
while(!Q.empty()) {
auto it = Q.front(); Q.pop();
int ux = it.first, uy = it.second;
for(int k = 0; k < 4; k++) {
int tx = ux + dx[k];
int ty = uy + dy[k];
if(min(tx,ty) < 0 || max(tx,ty) >= n || mat[tx][ty] == 'T' || mat[tx][ty] == 'D' || beeDist[ux][uy] + S >= beeDist[tx][ty]) continue;
beeDist[tx][ty] = beeDist[ux][uy] + S;
Q.push(make_pair(tx,ty));
}
}
int lo = 0, hi = n * n, ans = -1;
while(lo <= hi) {
int mid = (lo + hi) >> 1;
if(call(mid)) ans = mid, lo = mid+1;
else hi = mid-1;
} cout << ans << "\n";
return 0;
}
