#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 805;
const int oo = 1e9;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
char a[N][N];
pair <int, int> s,t;
int bee[N][N];
int dis[N][N];
int n,d;
bool ok(int i, int j) {
return a[i][j] != 'T' && min(i, j) > 0 && max(i, j) <= n;
}
bool solve(int x, queue <pair <int, int>> q) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (a[i][j] != 'H')
bee[i][j] = oo;
if (a[i][j] != 'M')
dis[i][j] = oo;
}
int fir = -1;
while (q.size()) {
int i = q.front().fi;
int j = q.front().se;
if (fir < 0)
fir = bee[i][j];
if (bee[i][j] - fir == x)
break;
q.pop();
for (int dir = 0; dir < 4; dir++) {
int u = i + dx[dir];
int v = j + dy[dir];
if (ok(u, v) && bee[u][v] == oo && a[u][v] != 'D') {
bee[u][v] = bee[i][j] + 1;
q.push(mp(u, v));
}
}
}
if (bee[s.fi][s.se] < oo)
return false;
queue <pair <int, int>> qq;
qq.push(s);
while (qq.size()) {
fir = -1;
while (qq.size()) {
int i = qq.front().fi;
int j = qq.front().se;
if (fir < 0)
fir = dis[i][j];
if (dis[i][j] - fir == d)
break;
qq.pop();
if (mp(i, j) == t)
return true;
if (bee[i][j] < oo)
continue;
for (int dir = 0; dir < 4; dir++) {
int u = i + dx[dir];
int v = j + dy[dir];
if (ok(u, v) && bee[u][v] == oo && dis[u][v] == oo) {
dis[u][v] = dis[i][j] + 1;
qq.push(mp(u, v));
}
}
}
fir = -1;
while (q.size()) {
int i = q.front().fi;
int j = q.front().se;
if (fir < 0)
fir = bee[i][j];
if (bee[i][j] - fir == 1)
break;
q.pop();
for (int dir = 0; dir < 4; dir++) {
int u = i + dx[dir];
int v = j + dy[dir];
if (ok(u, v) && bee[u][v] == oo && a[u][v] != 'D') {
bee[u][v] = bee[i][j] + 1;
q.push(mp(u, v));
}
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> d;
queue <pair <int, int>> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == 'H')
q.push(mp(i, j));
if (a[i][j] == 'M')
s = mp(i, j);
if (a[i][j] == 'D')
t = mp(i, j);
}
int lo = -1;
int hi = 1e9;
while (hi - lo > 1) {
int mid = (lo + hi) >> 1;
if (solve(mid, q))
lo = mid;
else
hi = mid;
}
cout << lo;
return 0;
}
