#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int,int>
const int N=805;
const int INF=1e6;
const int dy[]={-1,1,0,0};
const int dx[]={0,0,-1,1};
int n,m,d_b[N][N],d_m[N][N];
bool ck=false;
pii st,en;
queue <pii> q;
char c[N][N];
bool ok(int y,int x){
if(y<1 || y>n || x<1 || x>n) return false;
else return true;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
for(int i=0;i<N;i++) for(int j=0;j<N;j++) d_b[i][j]=INF;
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin >> c[i][j];
if(c[i][j]=='H'){
d_b[i][j]=0;
q.push({i,j});
}
else if(c[i][j]=='M') st={i,j};
else if(c[i][j]=='D') en={i,j};
}
}
while(!q.empty()){
auto [y,x]=q.front();
q.pop();
for(int i=0;i<4;i++){
int yy=y+dy[i],xx=x+dx[i];
if(!ok(yy,xx) || c[yy][xx]=='D' || c[yy][xx]=='T' || d_b[yy][xx]!=INF) continue;
d_b[yy][xx]=d_b[y][x]+m;
q.push({yy,xx});
}
}
int l=0,r=INF;
while(l<r){
int mid=(l+(r-l+1))/2;
memset(d_m,-1,sizeof(d_m));
q.push(st);
d_m[st.first][st.second]=mid*m;
while(!q.empty()){
auto [y,x]=q.front();
q.pop();
for(int i=0;i<4;i++){
int yy=y+dy[i],xx=x+dx[i];
if(!ok(yy,xx) || c[yy][xx]=='T' || d_m[yy][xx]!=-1 || d_m[y][x]+1>=d_b[yy][xx]) continue;
d_m[yy][xx]=d_m[y][x]+1;
q.push({yy,xx});
}
}
if(d_m[en.first][en.second]!=-1){
l=mid;
ck=true;
}
else r=mid-1;
}
if(l==0) cout << 1/0;
if(!ck) cout << -1;
else cout << l;
}
