#include <bits/stdc++.h>
using namespace std;
struct node
{
int i,j;
node(){}
node(int i,int j) : i(i),j(j){}
};
int n,s;
char board[805][805];
int bee[805][805];
int d[805][805];
int color[805][805];
int fuel[805][805];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
queue<node> Q;
node start,finish;
void bfsBee()
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
bee[i][j]=INT_MAX;
if(board[i][j]=='H'){
Q.push(node(i,j));
bee[i][j]=0;
color[i][j]=-1;
}
}
}
while(Q.size()){
node u=Q.front();Q.pop();
for(int mov=0;mov<4;mov++){
int i=u.i+dx[mov];
int j=u.j+dy[mov];
if(i<1 || i>n) continue;
if(j<1 || j>n) continue;
if(board[i][j]=='T' || board[i][j]=='D') continue;
if(color[i][j]==0){
color[i][j]=-1;
Q.push(node(i,j));
bee[i][j]=bee[u.i][u.j]+1;
}
}
}
}
void bfsMecho(int init_d)
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=INT_MAX;
color[i][j]=0;
}
}
if(bee[start.i][start.j]<=init_d-1) return;
d[start.i][start.j]=init_d-1;
fuel[start.i][start.j]=0;
color[start.i][start.j]=init_d;
Q.push(start);
while(Q.size()){
node u=Q.front();Q.pop();
if(d[u.i][u.j]==bee[u.i][u.j] && fuel[u.i][u.j]==0) continue;
for(int mov=0;mov<4;mov++){
int i=u.i+dx[mov];
int j=u.j+dy[mov];
if(i<1 || i>n) continue;
if(j<1 || j>n) continue;
if(board[i][j]=='T') continue;
if(color[i][j]!=init_d){
d[i][j]=(fuel[u.i][u.j]>0)? d[u.i][u.j] : d[u.i][u.j]+1;
if(bee[i][j]<d[i][j]) continue;
fuel[i][j]=(fuel[u.i][u.j]>0)? fuel[u.i][u.j]-1 : s-1;
color[i][j]=init_d;
Q.push(node(i,j));
}
}
}
}
bool valid(int k)
{
bfsMecho(k);
return d[finish.i][finish.j]!=INT_MAX;
}
int binarySearch()
{
int k=0;
for(int b=10000;b>=1;b/=2){
while(valid(k+b)) k+=b;
}
return k-1;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>s;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>board[i][j];
if(board[i][j]=='M') start={i,j};
if(board[i][j]=='D') finish={i,j};
}
}
bfsBee();
int maximum=binarySearch();
cout<<maximum<<'\n';
return 0;
}
