#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=1000;
char a[N][N];
int xx[4]={1,-1,0,0};
int yy[4]={0,0,-1,1};
bool vis[N][N],tkn[N][N];
signed main(){
int n,k;
cin>>n>>k;
int Y,X;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]=='D'){
Y=i;X=j;
}
}
}
int lo=0,hi=n*n;
while(hi>=lo){
int mid=(hi+lo)/2;
queue<vector<int>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
tkn[i][j]=vis[i][j]=0;
if(a[i][j]=='H'){
q.push({i,j,0});
tkn[i][j]=1;
}
}
}
while(!q.empty()){
auto v=q.front();
q.pop();
int y=v[0],x=v[1],w=v[2];
if(w==mid)continue;
for(int i=0;i<4;i++){
int y2=y+yy[i],x2=x+xx[i];
if(y2>=1 and y2<=n and x2>=1 and x2<=n and tkn[y2][x2]==0 and a[y2][x2]!='T'){
tkn[y2][x2]=1;
q.push({y2,x2,w+1});
}
}
}
vector<vector<int>>bees;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(tkn[i][j]){
bees.pb({i,j});
}
if(a[i][j]=='M'){
q.push({i,j,0});
vis[i][j]=1;
}
}
}
bool u=1;
while(!q.empty()){
auto v=q.front();
q.pop();
int y=v[0],x=v[1],w=v[2];
if(w%k==0 and u){
u=0;
vector< vector<int>>tmp;
for(auto p:bees){
int y=p[0],x=p[1];
for(int i=0;i<4;i++){
int y2=y+yy[i],x2=x+xx[i];
if(y2>=1 and y2<=n and x2>=1 and x2<=n and tkn[y2][x2]==0 and a[y2][x2]!='T'){
tkn[y2][x2]=1;
tmp.pb({y2,x2});
}
}
}
swap(bees,tmp);
}
if(w%k)u=1;
for(int i=0;i<4;i++){
int y2=y+yy[i],x2=x+xx[i];
if(y2>=1 and y2<=n and x2>=1 and x2<=n and tkn[y2][x2]==0 and a[y2][x2]!='T' and tkn[y2][x2]==0){
q.push({y2,x2,w+1});
vis[y2][x2]=1;
}
}
}
if(vis[Y][X])lo=mid+1;
else hi=mid-1;
}
cout<<lo;
}
