#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 && mid*m<d_b[st.first][st.second]){ l=mid; ck=true; } else r=mid-1; } if(!ck) cout << -1; else cout << l; }