#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
int n,S,vis[805][805],tim[805][805];
pair<int,int> st,ed,bck[805][805];
char c[805][805];
vector<pair<int,int>> d,path;
queue<pair<pair<int,int>,pair<int,int>>> q;
bool ok(int x,int y){
return (1<=x && x<=n && 1<=y && y<=n);
}
bool pass(int T){
T*=S;
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) vis[i][j]=0;
queue<pair<pair<int,int>,int>> t; t.push(mp(st,T));
while (!t.empty()){
auto x=t.front(); t.pop();
if (x.f==ed) vis[x.f.f][x.f.s]=x.s;
else if (x.s>=(tim[x.f.f][x.f.s]-1)*S || vis[x.f.f][x.f.s]) continue;
vis[x.f.f][x.f.s]=x.s;
for (auto k:d){
int a=x.f.f+k.f; int b=x.f.s+k.s;
if (ok(a,b) && c[a][b]!='T') t.push(mp(mp(a,b),x.s+1));
}
}
return vis[ed.f][ed.s];
}
int main() {
cin>>n>>S;
d.push_back({1,0}); d.push_back({-1,0});
d.push_back({0,-1}); d.push_back({0,1});
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
cin>>c[i][j];
if (c[i][j]=='D') ed=mp(i,j);
if (c[i][j]=='M') st=mp(i,j);
}
}
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (c[i][j]=='H') q.push(mp(mp(i,j),mp(0,0)));
}
}
while (!q.empty()){
auto x=q.front(); q.pop();
if (tim[x.f.f][x.f.s]) continue;
tim[x.f.f][x.f.s]=tim[x.s.f][x.s.s]+1;
for (auto k:d){
int a=x.f.f+k.f; int b=x.f.s+k.s;
if (ok(a,b) && c[a][b]!='T') q.push(mp(mp(a,b),x.f));
}
}
tim[ed.f][ed.s]=INT_MAX;
if (pass(0)){
int ans=0;
int l=0; int r=n*n+5;
while (l<=r){
int mid=(l+r)/2;
if (pass(mid)){
ans=mid; l=mid+1;
}
else r=mid-1;
}
cout<<ans<<"\n";
}
else cout<<"-1\n";
}
