#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 805;
int N, S, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
char a[MN][MN];
int bee[MN][MN], dis[MN][MN];
int sx, sy, ex, ey;
bool good(int t) {
if (t >= bee[sx][sy]) return false;
memset(dis, 0x3f, sizeof(dis));
dis[sx][sy] = t + 1;
queue<pair<pii, int>> q;
q.push({{sx, sy}, S});
while (!q.empty()) {
auto [p, s] = q.front(); q.pop();
auto [x, y] = p;
if (!s && dis[x][y] >= bee[x][y]) continue;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < 1 || nx > N || ny < 1 || ny > N || a[nx][ny] == 'T') continue;
if (!s) {
int nd = dis[x][y] + 1;
if (dis[nx][ny] > nd && nd <= bee[nx][ny]) {
dis[nx][ny] = nd;
q.push({{nx, ny}, S - 1});
}
} else {
int nd = dis[x][y];
if (dis[nx][ny] > nd && nd <= bee[nx][ny]) {
dis[nx][ny] = nd;
q.push({{nx, ny}, s - 1});
}
}
}
}
return dis[ex][ey] < 1e9;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> S;
queue<pii> q;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) {
cin >> a[i][j];
bee[i][j] = 1e9;
if (a[i][j] == 'M') sx = i, sy = j;
if (a[i][j] == 'D') ex = i, ey = j;
if (a[i][j] == 'H') q.emplace(i, j), bee[i][j] = 0;
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < 1 || nx > N || ny < 1 || ny > N || a[nx][ny] == 'T' || a[nx][ny] == 'D') continue;
if (bee[nx][ny] > bee[x][y] + 1) bee[nx][ny] = bee[x][y] + 1, q.emplace(nx, ny);
}
}
int l = 0, r = 5e5;
while (l < r) {
int m = (l + r) / 2;
if (!good(m)) r = m;
else l = m + 1;
}
cout << l - 1 << '\n';
return 0;
}
