#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
#define ciii(x, y, z) ci(x); ci(y); ci(z)
#define mp make_pair
//#define int long long
typedef long long ll;
typedef vector<int> vi;
const int N = 8e2 + 5;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int pi = 31;
const int inf = 1e9 + 5;
const int block = 330;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
void readfile(){
#ifdef ONLINE_JUDGE
#else
freopen("text.inp", "r", stdin);
#endif // ONLINE_JUDGE
// freopen("gravity.in", "r", stdin);
// freopen("gravity.out", "w", stdout);
}
int n, s;
char a[N][N];
pair<int,int> st, e;
void inp(){
cin >> n >> s;
rep(i,1,n)
rep(j,1,n){
cin >> a[i][j];
if(a[i][j]=='M')
st = mp(i, j);
if(a[i][j]=='D')
e = mp(i, j);
}
}
int d[N][N], d1[N][N];
void bfs_multi_source(){
queue<pair<int,int> > q;
rep(i,1,n)
rep(j,1,n){
d1[i][j] = inf;
if(a[i][j]=='H')
q.push(mp(i ,j)), d1[i][j] = 0;
}
while(!q.empty()){
pair<int,int> top = q.front();
q.pop();
rep(i,0,3){
int x = top.fi + dx[i];
int y = top.se + dy[i];
if(1 <= x && x <= n && 1 <= y && y <= n && a[x][y]!='T' && a[x][y]!='D' && d1[x][y] > d1[top.fi][top.se] + 1){
d1[x][y] = d1[top.fi][top.se] + 1;
q.push(mp(x,y));
}
}
}
}
int vis[N][N], m[N][N];
void bfs(int x, int y, int ti){
rep(i,1,n)
rep(j,1,n)
d[i][j] = inf, vis[i][j] = 0;
queue<pair<int,int> > q;
q.push(mp(x, y));
d[x][y] = ti;
if(ti >= d1[x][y]) return;
while(!q.empty()){
auto top = q.front();
q.pop();
vis[top.fi][top.se] = 1;
rep(i,0,3){
int x = top.fi + dx[i];
int y = top.se + dy[i];
if(1 <= x && x <= n && 1 <= y && y <= n && a[x][y]!='T' && d[x][y] > d[top.fi][top.se] + 1){
d[x][y] = d[top.fi][top.se] + 1;
m[x][y] = (m[top.fi][top.se] + 1) % s;
int diff = d[x][y] - ti - 1;
diff /= s;
diff += ti + 1;
if(diff < d1[x][y] || (diff==d1[x][y] && m[x][y]))
q.push(mp(x, y));
}
}
}
}
void process(){
bfs_multi_source();
int l = 0, r = n*n + 1, res = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(mid==240)
int h = 0;
bfs(st.fi, st.se, mid);
if(!vis[e.fi][e.se])
r = mid - 1;
else{
res = mid;
l = mid + 1;
}
}
cout << res;
}
int main() {
//readfile();
ios_base::sync_with_stdio(0);
cin.tie(0);
// TC(t){
inp();
process();
// }
return 0;
}
