#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N=805;
int n,ANS=-1,k,Timer[N][N],F[N][N];
char c[N][N];
pair < int , int > a[6],Home,Honeypot;
vector < pair < int , int > > Hive;
void Bfs () {
queue < pair < int , int > > q;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
Timer[i][j]=1e9;
for (int i=0; i<Hive.size(); i++)
q.push(Hive[i]),Timer[Hive[i].F][Hive[i].S]=0;
while (!q.empty()) {
pair < int , int > B=q.front();
q.pop();
for (int i=1; i<=4; i++) {
int X=B.F+a[i].F,Y=B.S+a[i].S;
if (!(1<=X && X<=n && 1<=Y && Y<=n)) continue;
if (c[X][Y]=='T' || c[X][Y]=='D' || Timer[X][Y]!=1e9) continue;
Timer[X][Y]=Timer[B.F][B.S]+k;
q.push({X,Y});
}
}
}
bool check(int x) {
if (x*k>=Timer[Honeypot.F][Honeypot.S]) return 0;
queue < pair < pair < int , int > , int > > Q;
while (!Q.empty()) Q.pop();
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
F[i][j]=0;
Q.push({{Honeypot.F,Honeypot.S},(x*k)});
F[Honeypot.F][Honeypot.S]=1;
while (!Q.empty()) {
pair < int , int > D=Q.front().F;
int timer=Q.front().S;
Q.pop();
if (c[D.F][D.S]=='D') return 1;
for (int i=1; i<=4; i++) {
int X=D.F+a[i].F,Y=D.S+a[i].S;
if (!(1<=X && X<=n && 1<=Y && Y<=n)) continue;
if (Timer[X][Y]<=timer+1 || F[X][Y] || c[X][Y]=='T') continue;
Q.push({{X,Y},timer+1});
F[X][Y]=1;
}
}
return 0;
}
main () {
a[1].F=1; a[1].S=0;
a[2].F=-1; a[2].S=0;
a[3].F=0; a[3].S=1;
a[4].F=0; a[4].S=-1;
cin>>n>>k;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++){
cin>>c[i][j];
if (c[i][j]=='M') Honeypot.F=i,Honeypot.S=j;
if (c[i][j]=='H') Hive.push_back({i,j});
if (c[i][j]=='D') Home.F=i,Home.S=j;
}
Bfs();
int l=0,r=n*n,mid=0;
while (l<=r) {
mid=(l+r)/2;
if (check(mid)) { ANS=mid; l=mid+1; }
else r=mid-1;
}
cout<<ANS<<endl;
}
