#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 810, inf = 1e9;
const int mv[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n, s, mx, my, dx, dy, d1[MAXN][MAXN], d2[MAXN][MAXN];
char g[MAXN][MAXN];
// bfs
bool valid(int x, int y){
return x >= 1 && x <= n && y >= 1 && y <= n;
}
void bfs1(){
queue<pii> q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(g[i][j] == 'H')
d1[i][j] = 0, q.push(mp(i, j));
else d1[i][j] = inf;
while(!q.empty()){
pii u = q.front(); q.pop();
for(int k = 0; k < 4; k++){
int x = u.fi + mv[k][0];
int y = u.se + mv[k][1];
if(valid(x, y) && g[x][y] != 'T' && g[x][y] != 'D' && d1[x][y] == inf){
d1[x][y] = d1[u.fi][u.se] + 1;
q.push(mp(x, y));
}
}
}
}
bool check(int t){
queue<pii> q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
d2[i][j] = inf;
if(t < d1[mx][my])
d2[mx][my] = 0, q.push(mp(mx, my));
while(!q.empty()){
pii u = q.front(); q.pop();
for(int k = 0; k < 4; k++){
int x = u.fi + mv[k][0];
int y = u.se + mv[k][1];
if(valid(x, y) && g[x][y] != 'T' && d2[x][y] == inf && (t + (d2[u.fi][u.se] + 1) / s < d1[x][y])){
d2[x][y] = d2[u.fi][u.se] + 1;
q.push(mp(x, y));
}
}
}
return d2[dx][dy] != inf;
}
int main(){
// input
scanf("%d %d", &n, &s);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
scanf(" %c", &g[i][j]);
if(g[i][j] == 'M')
mx = i, my = j;
if(g[i][j] == 'D')
dx = i, dy = j;
}
// prework(bfs)
bfs1();
// binary search
int l = -1, r = n * n, mid;
while(l < r){
mid = (l + r + 1) / 2;
if(check(mid))
l = mid;
else r = mid - 1;
}
printf("%d\n", l);
}
