#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=810,inf=1e9;
vector<pair<int,int>>ds={{0,1},{0,-1},{1,0},{-1,0}};
int n,S;
string a[N];
int dist1[N][N];
bool was[N][N];
bool Check(int i,int j){
if(i<0||i>=n||j<0||j>=n)return false;
if(a[i][j]=='T'||was[i][j])return false;
return true;
}
int dist[N][N],dist2[N][N];
bool BFS(int t){
queue<pair<int,int>>kju;
int U,V;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
dist[i][j]=inf;was[i][j]=false;
if(a[i][j]=='M')dist[i][j]=0,was[i][j]=true,kju.push({i,j});
if(a[i][j]=='D')U=i,V=j;
}
while(!kju.empty()){
auto [i,j]=kju.front();kju.pop();
for(auto [dx,dy]:ds)if(Check(i+dx,j+dy)){
if((dist[i][j]%S!=S-1&&dist[i][j]/S+1<=dist1[i+dx][j+dy]-t)||(dist[i][j]%S==S-1&&dist[i][j]/S+1<dist1[i+dx][j+dy]-t)){
dist[i+dx][j+dy]=dist[i][j]+1;
kju.push({i+dx,j+dy});
was[i+dx][j+dy]=true;
}
}
}
return dist[U][V]<inf;
}
int main(){
scanf("%i%i",&n,&S);
for(int i=0;i<n;i++)cin>>a[i];
queue<pair<int,int>>kju;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
dist1[i][j]=inf;
if(a[i][j]=='H')dist1[i][j]=0,kju.push({i,j}),was[i][j]=true;
}
while(!kju.empty()){
auto [i,j]=kju.front();kju.pop();
for(auto [dx,dy]:ds)if(Check(i+dx,j+dy)&&a[i+dx][j+dy]!='D'){
dist1[i+dx][j+dy]=dist1[i][j]+1;
kju.push({i+dx,j+dy});
was[i+dx][j+dy]=true;
}
}
int U,V;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(a[i][j]=='M')U=i,V=j;
int l=0,r=dist1[U][V]-1,res=-1;
while(l<=r){
int mid=l+r>>1;
if(BFS(mid))res=mid,l=mid+1;
else r=mid-1;
}
printf("%i\n",res);
return 0;
}
