#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int iini, ifin, jini, jfin, n, s;
bool way_home(int m, vector<vector<int> >&bemoment, vector<vector<char> >&grid){
queue<pair<int,int> >mecho;
vector<vector<pair<int,int> > >mechomoment(n, vector<pair<int,int> >(n, make_pair(1e9, 0)));
mecho.push(make_pair(iini, jini));
mechomoment[iini][jini]=make_pair(m, 1);
while (!mecho.empty()){
int i=mecho.front().first;
int j=mecho.front().second;
mecho.pop();
int minut=mechomoment[i][j].first, steps=mechomoment[i][j].second;
if (steps==s){
minut++;
steps=0;
}steps++;
if ((i!=0 && grid[i-1][j]=='D')||(j!=0 && grid[i][j-1]=='D')||(i!=n-1 && grid[i+1][j]=='D')||((j!=n-1 && grid[i][j+1]=='D'))){
return true;
}
if (i!=0 and bemoment[i-1][j]>minut and mechomoment[i-1][j].first==1e9){
mechomoment[i-1][j]=make_pair(minut, steps);
mecho.push(make_pair(i-1, j));
}if (j!=0 and bemoment[i][j-1]>minut and mechomoment[i][j-1].first==1e9){
mechomoment[i][j-1]=make_pair(minut, steps);
mecho.push(make_pair(i, j-1));
}if (i!=n-1 and bemoment[i+1][j]>minut and mechomoment[i+1][j].first==1e9){
mechomoment[i+1][j]=make_pair(minut, steps);
mecho.push(make_pair(i+1, j));
}if (j!=n-1 and bemoment[i][j+1]>minut and mechomoment[i][j+1].first==1e9){
mechomoment[i][j+1]=make_pair(minut, steps);
mecho.push(make_pair(i, j+1));
}
}return false;
}
int main(){
cin>>n>>s;
vector<vector<char> >grid(n, vector<char>(n));
vector<vector<int> >bemoment(n, vector<int>(n, 1e9));
queue<pair<int,int> >grassy;
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
cin>>grid[i][j];
if (grid[i][j]=='H'){
grassy.push(make_pair(i, j));
bemoment[i][j]=0;
}else if (grid[i][j]=='M'){
iini=i;
jini=j;
}else if (grid[i][j]=='D'){
ifin=i;
jfin=j;
bemoment[i][j]=-1;
}else if (grid[i][j]=='T') bemoment[i][j]=-1;
}
}while (!grassy.empty()){
int i=grassy.front().first;
int j=grassy.front().second;
grassy.pop();
if (i!=0 and bemoment[i-1][j]==1e9){
bemoment[i-1][j]=bemoment[i][j]+1;
grassy.push(make_pair(i-1, j));
}if (j!=0 and bemoment[i][j-1]==1e9){
bemoment[i][j-1]=bemoment[i][j]+1;
grassy.push(make_pair(i, j-1));
}if (i!=n-1 and bemoment[i+1][j]==1e9){
bemoment[i+1][j]=bemoment[i][j]+1;
grassy.push(make_pair(i+1, j));
}if (j!=n-1 and bemoment[i][j+1]==1e9){
bemoment[i][j+1]=bemoment[i][j]+1;
grassy.push(make_pair(i, j+1));
}
}int ans=-1;
int l=0, r=bemoment[iini][ifin]-1, m;
while (l<=r){
m=(r-l)/2+l;
if (l+1==r){
if (way_home(r, bemoment, grid)){
ans=r;
l+=2;
}else if (way_home(l, bemoment, grid)){
ans=l;
r-=2;
}else ans=-1;
break;
}else if (l==r){
if (way_home(r, bemoment, grid)){
ans=r;
l++;
}else ans=-1;
break;
}
if (way_home(m, bemoment, grid)) l=m;
else r=m-1;
}cout<<ans<<'\n';
return 0;
}
