#include<bits/stdc++.h>
using namespace std;
const int N=2000009;
int a,c,d,e,i,j,ii,jj,zx,xc,S,B[809][809],lef,rig,mid,f[809][809],Mi,Mj,X[809][809],dis[809][809],Di,Dj;
bool bo[809][809];
string s;
char ch[809][809];
deque <pair <int, int> > de;
void chk(int q, int w){
if(q<1||q>a||w<1||w>a) return;
if(f[q][w]==0) return;
if(B[q][w]>B[i][j]+1){
B[q][w]=B[i][j]+1;
de.push_back({q,w});
}
}
void CHK(int q, int w){
if(q<1||q>a||w<1||w>a) return;
if(f[q][w]==0) return;
if(bo[q][w]==1) return;
if(dis[i][j]+1>X[q][w]) return;
bo[q][w]=1;
dis[q][w]=dis[i][j]+1;
de.push_back({q,w});
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>S;
for(i=1; i<=a; i++){
cin>>s;
for(j=1; j<=a; j++){
ch[i][j]=s[j-1];
}
}
for(i=0; i<=a+1; i++){
for(j=0; j<=a+1; j++){
B[i][j]=N;
}
}
for(i=1; i<=a; i++){
for(j=1; j<=a; j++){
if(ch[i][j]=='H'){
de.push_back({i,j});
B[i][j]=0;
}
if(ch[i][j]=='T'||ch[i][j]=='D'){
f[i][j]=0;
}else{
f[i][j]=1;
}
if(ch[i][j]=='M'){
Mi=i;Mj=j;
}
if(ch[i][j]=='D'){
Di=i;Dj=j;
}
}
}
while(de.size()){
i=de.front().first;j=de.front().second;
de.pop_front();
chk(i+1,j);chk(i-1,j);chk(i,j+1);chk(i,j-1);
}
/*for(i=1; i<=a; i++){
for(j=1; j<=a; j++){
cout<<B[i][j]<<" ";
}
cout<<"\n";
}*/
lef=-1;rig=a*a+2;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
if(B[Mi][Mj]<=mid){
rig=mid;
continue;
}
for(i=1; i<=a; i++){
for(j=1; j<=a; j++){
if(ch[i][j]=='T'||ch[i][j]=='H'){
f[i][j]=0;
}else{
f[i][j]=1;
}
bo[i][j]=0;
if(B[i][j]<=mid){
X[i][j]=-1;
}else{
zx=B[i][j]-mid;
X[i][j]=zx*S-1;
}
}
}
while(de.size()) de.pop_back();
de.push_back({Mi,Mj});bo[Mi][Mj]=1;dis[Mi][Mj]=0;
while(de.size()){
i=de.front().first;j=de.front().second;
de.pop_front();
CHK(i+1,j);CHK(i-1,j);CHK(i,j+1);CHK(i,j-1);
}
if(bo[Di][Dj]==1){
lef=mid;
}else{
rig=mid;
}
}
cout<<lef;
return 0;
}
