#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ii,ii> iii;
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define N 1000005
#define M 1005
#define MOD 1000000007
ll dx[] = { 1, 0, 0, -1 };
ll dy[] = { 0, -1, 1, 0 };
ll n,s;
ii u,v;
ll d[M][M];
ll dist[M][M];
bool f[M][M];
bool c[M][M];
char a[M][M];
queue <ii> q1;
queue <ii> q;
void debug(){
for (long i=1; i<=n; i++){
for (long j=1; j<=n; j++) cerr << dist[i][j]<< ' ';
cerr << endl;
}
}
bool check(ll x,ll y,ll mid){
return ((dist[x][y] + 1) / s) + mid < d[x][y];
}
void setup(){
for (long i=1; i<=n; i++){
for (long j=1; j<=n; j++){
if (a[i][j] != 'H') d[i][j] = 1e9;
}
}
while (!q1.empty()){
ii t = q1.front(); q1.pop();
for (long i=0; i<4; i++){
ll x = t.fi + dx[i];
ll y = t.se + dy[i];
if (x >= 1 && y >= 1 && x <= n && y <= n && !f[x][y] && d[x][y] > d[t.fi][t.se] + 1 && a[x][y] != 'D' && a[x][y] != 'T'){
f[x][y] = 1;
d[x][y] = d[t.fi][t.se] + 1;
q1.push({x,y});
}
}
}
}
bool bfs(ll mid){
for (long i=1; i<=n; i++){
for (long j=1; j<=n; j++){
c[i][j] = 0;
dist[i][j] = 1e9;
}
}
c[u.fi][u.se] = 1;
dist[u.fi][u.se] = 0;
q.push(u);
if (mid >= d[u.fi][u.se]) return 0;
while (!q.empty()){
ii t2 = q.front();
q.pop();
for (long i=0; i<4; i++){
ll x = t2.fi + dx[i];
ll y = t2.se + dy[i];
if (x >= 1 && y >= 1 && x <= n && y <= n && dist[x][y] > dist[t2.fi][t2.se] + 1 && !c[x][y] && a[x][y] != 'T' && (dist[t2.fi][t2.se] + 1) / s + mid < d[x][y]){
c[x][y] = 1;
dist[x][y] = dist[t2.fi][t2.se] + 1;
q.push({x,y});
}
}
}
return c[v.fi][v.se];
}
signed main(){
// #ifndef ONLINE_JUDGE
// freopen("test.inp", "r", stdin);
// freopen("test.out" ,"w", stdout);
// #endif
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> s;
for (long i=1; i<=n; i++){
for (long j=1; j<=n; j++){
cin >> a[i][j];
if (a[i][j] == 'M'){
u.fi = i;
u.se = j;
}
if (a[i][j] == 'D'){
v.fi = i;
v.se = j;
}
if (a[i][j] == 'H'){
q1.push({i,j});
d[i][j] = 0;
f[i][j] = 1;
}
}
}
setup();
ll l = 0, r = 800 * 800;
ll res = -1;
while (l <= r){
ll mid = l + r >> 1;
if (bfs(mid)){
l = mid + 1;
res = mid;
} else r = mid - 1;
}
cout << res;
return 0;
}
