#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];
const int inf=1e18;
const int N=800;
string a[N];
int d[N][N];
int p[N][N];
int vis[N][N];
void clear(int n) {
forn(i,n) forn(j,n) d[i][j]=0;
}
void reset(int n) {
forn(i,n) forn(j,n) vis[i][j]=0;
}
struct z {
int f,s,d,d1,d2;
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n,s; cin>>n>>s;
forn(i,n) cin>>a[i];
forn(i,n) forn(j,n) p[i][j]=inf;
queue<z> q;
forn(i,n) forn(j,n) if (a[i][j]=='H') {
q.push({i,j,0});
}
while (q.size()) {
auto it=q.front(); q.pop();
int x=it.f, y=it.s, d=it.d;
if (x<0 || y<0) continue;
if (x>=n || y>=n) continue;
if (vis[x][y]) continue;
if (a[x][y]=='T' || a[x][y]=='D') continue;
vis[x][y]=1;
p[x][y]=d;
q.push({x-1,y,d+1});
q.push({x+1,y,d+1});
q.push({x,y-1,d+1});
q.push({x,y+1,d+1});
}
int l=-1, r=1e9;
pi D;
forn(i,n) forn(j,n) if (a[i][j]=='D') D={i,j};
while (l<r) {
int mid=(l+r+1)>>1;
reset(n);
forn(i,n) forn(j,n) if (a[i][j]=='M') {
q.push({i,j,0,0,0});
}
while (q.size()) {
auto it=q.front(); q.pop();
int x=it.f, y=it.s, d=it.d, d1=it.d1, d2=it.d2;
//cout<<mid<<": "<<x<<' '<<y<<' '<<d<<' '<<vis[x][y]<<' '<<p[x][y]<<' '<<a[x][y]<<'\n';
if (x<0 || y<0) continue;
if (x>=n || y>=n) continue;
if (vis[x][y]) continue;
if (a[x][y]=='T') continue;
if (p[x][y]<mid+(d+s-1)/s) continue;
if (p[x][y]==mid+(d+s-1)/s) {
if (d%s) {
} else {
continue;
}
}
vis[x][y]=1;
q.push({x-1,y,d+1});
q.push({x+1,y,d+1});
q.push({x,y-1,d+1});
q.push({x,y+1,d+1});
}
if (vis[D.f][D.s]) l=mid;
else r=mid-1;
}
cout<<r<<'\n';
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
