#include<bits/stdc++.h>
using namespace std;
vector<string> a;
int en[810][810],b[810][810];
queue<tuple<int,int,int>> qn,qb;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int hi,hj,n,s;
bool cal(int mid){
while(!qb.empty()) qb.pop();
while(!qn.empty()) qn.pop();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
en[i][j]=b[i][j]=false;
if(a[i][j]=='H') qn.push({-1,i,j}),en[i][j]=true;
else if(a[i][j]=='M') qb.push({-1,i,j}),b[i][j]=true;
}
}
queue<tuple<int,int,int>> tqn,tqb;
while(!qn.empty()){
auto [d,x,y]=qn.front();
qn.pop();
en[x][y]=1;
if(d==0){
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
if(a[nx][ny]=='T' || a[nx][ny]=='D') continue;
if(en[nx][ny]) continue;
en[nx][ny]=2;
tqn.push({0,nx,ny});
continue;
}
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
if(a[nx][ny]=='T' || a[nx][ny]=='D') continue;
if(en[nx][ny]) continue;
en[nx][ny]=true;
if(d==-1) d=mid;
qn.push({d-1,nx,ny});
}
}
//for(int i=0;i<n;i++) for(int j=0;j<n;j++) cout<<en[i][j] <<" \n"[j==n-1];
qn=tqn;
while(!tqb.empty()) tqb.pop();
while(!tqn.empty()) tqn.pop();
int c=0;
//<<"hi\n";
while(!qb.empty()){
//cout<<"loop\n";
//<<"\n";
while(!qb.empty()){
auto [d,x,y]=qb.front();
qb.pop();
b[x][y]=1;
if(en[x][y]==1) continue;
if(d==0){
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
if(a[nx][ny]=='T' || a[nx][ny]=='H') continue;
if(en[nx][ny] || b[nx][ny]) continue;
b[nx][ny]=2;
tqb.push({s,nx,ny});
}
continue;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
if(a[nx][ny]=='T' || a[nx][ny]=='H') continue;
if(en[nx][ny]==1 || b[nx][ny]) continue;
b[nx][ny]=true;
if(d==-1) d=s;
qb.push({d-1,nx,ny});
}
}
//(int i=0;i<n;i++) for(int j=0;j<n;j++) cout<<b[i][j] <<" \n"[j==n-1];
//cout<<"\n";
qb=tqb;
while(!qn.empty()){
auto [d,x,y]=qn.front();
qn.pop();
en[x][y]=1;
if(d==0){
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
if(a[nx][ny]=='T' || a[nx][ny]=='D') continue;
if(en[nx][ny]) continue;
en[nx][ny]=2;
tqn.push({0,nx,ny});
}
continue;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
if(a[nx][ny]=='T' || a[nx][ny]=='D') continue;
if(en[nx][ny]) continue;
en[nx][ny]=true;
if(d==-1) d=1;
qn.push({d-1,nx,ny});
}
}
//for(int i=0;i<n;i++) for(int j=0;j<n;j++) cout<<en[i][j] <<" \n"[j==n-1];
qn=tqn;
while(!tqn.empty()) tqn.pop();
while(!tqb.empty()) tqb.pop();
}
return b[hi][hj]==1;
}
int main(){
cin>>n >>s;
for(int i=0;i<n;i++){
string tmp; cin>>tmp;
a.push_back(tmp);
for(int j=0;j<n;j++) if(tmp[j]=='D') hi=i,hj=j;
}
int l=0,r=2*n;
while(l<r){
int mid=(l+r+1)/2;
if(cal(mid)) l=mid;
else r=mid-1;
}
if(l==0 && cal(l)==0) cout<<-1;
else cout<<l;
}
