#include"bits/stdc++.h"
#define f(i,j,k) for(int i=j;i<=k;i++)
#define fi first
#define se second
#define mp make_pair
const int N = 808;
const int oo = 2e9;
const int C[] = {0,1,0,-1,0};
using namespace std;
using pii = pair<int,int>;
int n, s;
int f[N][N], cx[N][N];
char a[N][N];
pii st, ed;
struct dota{
int x, y, tim;
};
bool check(int t){
queue<dota> q;
memset(cx,0,sizeof(cx));
f(i,1,n) f(j,1,n) if(a[i][j] != 'T') cx[i][j] = 1;
q.push({st.fi,st.se,0});
cx[st.fi][st.se] = 0;
while(q.size()){
dota td = q.front(); q.pop();
int x = td.x;
int y = td.y;
int tim = td.tim;
//if(t == 1) cout<<x<<" "<<y<<" "<<tim<<endl;
if(x == ed.fi && y == ed.se) return true;
f(i,0,3){
int u = x + C[i];
int v = y + C[i+1];
if(cx[u][v] && (tim + 1)/s < f[u][v]-t){
q.push({u,v,tim+1});
cx[u][v] = 0;
}
}
}
return false;
}
main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>s;
f(i,1,n) f(j,1,n) cin>>a[i][j];
queue<pii> q;
memset(cx,0,sizeof(cx));
f(i,0,n) cx[i][0] = cx[0][i] = cx[i][n+1] = cx[n+1][i] = 1;
f(i,1,n) f(j,1,n){
if(a[i][j] == 'T') cx[i][j] = 1;
if(a[i][j] == 'H'){
cx[i][j] = 1;
q.push({i,j});
f[i][j] = 0;
}
if(a[i][j] == 'D') ed = mp(i,j), cx[i][j] = 1;
if(a[i][j] == 'M') st = mp(i,j);
}
while(q.size()){
pii td = q.front(); q.pop();
int x = td.fi, y = td.se;
f(i,0,3){
int u = x + C[i];
int v = y + C[i+1];
if(!cx[u][v]){
f[u][v] = f[x][y]+1;
cx[u][v] = true;
q.push({u,v});
}
}
}
//cout<<"vcl";
f[ed.fi][ed.se] = oo;
// f(i,1,n){
// f(j,1,n) cout<<f[i][j]<<" ";
// cout<<endl;
// }
int l = 0, r = f[st.fi][st.se]-1, mid, ans = -1;
while(l <= r){
//cout<<l<<" "<<r<<" "<<mid<<endl;
mid = (l+r)/2;
if(check(mid)) ans = mid,l = mid+1;
else r = mid-1;
}
cout<<ans;
}
