#include <bits/stdc++.h>
using namespace std;
const int N=810;
typedef pair<int,int> pii;
char G[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int T[N][N],d[N][N],vis[N][N];
int n,s,sx,sy;
int bfs(int time){
if (time*s>=T[sx][sy])return 0;
memset(vis,0,sizeof(vis));
queue<pii> Q;
vis[sx][sy]=1;
Q.push(make_pair(sx*N+sy,time*s));
// printf("X=%d Y=%d dis=%d\n",sx,sy,time*s);
while(!Q.empty()){
int dis=Q.front().second;
int x=Q.front().first/N;
int y=Q.front().first%N;
Q.pop();
if (G[x][y]=='D')return 1;
for (int k=0;k<4;k++){
int X=x+dx[k],Y=y+dy[k];
if (X<1||X>N||Y<1||Y>N)continue;
if (G[X][Y]=='T')continue;
if (dis+1>=T[X][Y]||vis[X][Y])continue;
vis[X][Y]=1;
Q.push(make_pair(X*N+Y,dis+1));
// printf("X=%d Y=%d dis=%d\n",X,Y,dis+1);
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&s);
for (int i=1;i<=n;i++)scanf("%s",G[i]+1);
memset(T,-1,sizeof(T));
queue<int> bq;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
if (G[i][j]=='M')sx=i,sy=j;
if (G[i][j]=='D')T[i][j]=n*n*s;
if (G[i][j]=='H'){
T[i][j]=0;
bq.push(i*N+j);
}
}
while(!bq.empty()){
int x=bq.front()/N,y=bq.front()%N;
bq.pop();
for (int i=0;i<4;i++){
int X=x+dx[i],Y=y+dy[i];
if (x<1||x>n||y<1||y>n||T[X][Y]!=-1)continue;
if (G[X][Y]=='T'||G[X][Y]=='D')continue;
T[X][Y]=T[x][y]+s;
bq.push(X*N+Y);
}
}
int l=-1,r=n*n*2;
// while(l+1<r){
// int m=(l+r)/2;
// if (bfs(m))l=m;
// else r=m;
// }
for (int i=T[sx][sy]/s-1;i>=0;i--)
if (bfs(i)){
printf("%d\n",i);
return 0;
}
printf("%d\n",l);
}
