// source: https://oj.uz/problem/view/IOI09_mecho
#include<iostream>
#include<queue>
#define pa pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=802, oo=1e9;
constexpr int X[]={0,1,0,-1,0};
int n,s;
char c[N][N];
int Ong[N][N],Gau[N][N];
pa St,Fi;
queue<pa> q;
bool inside(int x,int y){
return 1<=x&&x<=n&&1<=y&&y<=n;
}
void BFSOng(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(c[i][j]=='H') Ong[i][j]=0, q.push({i,j});
else Ong[i][j]=oo;
}
while(!q.empty()){
pa P=q.front(); q.pop();
for(int k=0;k<4;k++){
int nx=P.fi+X[k], ny=P.se+X[k+1];
if(inside(nx,ny)&&c[nx][ny]!='D'&&c[nx][ny]!='T')
if(Ong[nx][ny]==oo) Ong[nx][ny]=Ong[P.fi][P.se]+1, q.push({nx,ny});
}
}
}
bool check(int x){
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(c[i][j]=='M') Gau[i][j]=0, q.push({i,j});
else Gau[i][j]=oo;
}
for(int i=x,step=s;!q.empty();i++,step+=s) while(!q.empty()){
pa P=q.front();
if(Gau[P.fi][P.se]==step) break;
if(P==Fi) return 1;
q.pop();
if(Ong[P.fi][P.se]<=i) continue;
for(int k=0;k<4;k++){
int nx=P.fi+X[k], ny=P.se+X[k+1];
if(inside(nx,ny)&&c[nx][ny]!='T')
if(Ong[nx][ny]>i&&Gau[nx][ny]==oo) Gau[nx][ny]=Gau[P.fi][P.se]+1, q.push({nx,ny});
}
}
return 0;
}
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>c[i][j];
if(c[i][j]=='M') St={i,j};
if(c[i][j]=='D') Fi={i,j};
}
BFSOng();
int l=0, r=Ong[St.fi][St.se], ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid, l=++mid;
else r=--mid;
}
cout<<ans;
return 0;
}
