#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
template<class X, class Y> bool maximize (X &x, const Y &y) {return x < y ? x = y, 1 : 0;}
template<class X, class Y> bool minimize (X &x, const Y &y) {return x > y ? x = y, 1 : 0;}
const int maxn = 800 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, s;
int idk[maxn][maxn];
char grid[maxn][maxn];
vector<pair<int, int>> bees;
int sx, sy;
bool inside(int x, int y) {return (1 <= x && x <= n && 1 <= y && y <= n && grid[x][y] != 'T');}
void prepare() {
memset(idk, 0x3f, sizeof idk);
queue<pair<int, int>> q;
for (auto i : bees) {
idk[i.fi][i.se] = 0;
q.push(i);
}
while (!q.empty()) {
int x = q.front().fi, y = q.front().se;
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (inside(nx, ny) && grid[nx][ny] != 'D' && idk[nx][ny] == INF) {
idk[nx][ny] = idk[x][y] + 1;
q.push({nx, ny});
}
}
}
}
// {current cell x, current cell y, current minute, current step count}
int dist[maxn][maxn];
struct state {
int x, y, timer, step;
};
bool bfs(int cur) {
if (cur == 0) return true;
if (idk[sx][sy] < cur) return false;
memset(dist, -1, sizeof dist);
dist[sx][sy] = cur;
queue<state> q;
q.push({sx, sy, cur, 0});
while (!q.empty()) {
int x = q.front().x, y = q.front().y;
int timer = q.front().timer, step = q.front().step;
if (grid[x][y] == 'D') return true;
q.pop();
if (step < s) {
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (inside(nx, ny) && dist[nx][ny] == -1 && idk[nx][ny] >= timer) {
if (step + 1 == s && idk[nx][ny] == timer) continue;
dist[nx][ny] = timer;
q.push({nx, ny, timer, step + 1});
}
}
}
if (step == s) {
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (inside(nx, ny) && dist[nx][ny] == -1 && idk[nx][ny] > timer) {
dist[nx][ny] = timer + 1;
q.push({nx, ny, timer + 1, 1});
}
}
}
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= n; ++j) cout << setw(2) << idk[i][j] << ' ';
// cout << '\n';
// }
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= n; ++j) cout << setw(2) << dist[i][j] << ' ';
// cout << '\n';
// }
return false;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
//freopen(".INP", "r", stdin);
//freopen(".OUT", "w", stdout);
cin >> n >> s;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> grid[i][j];
if (grid[i][j] == 'M') sx = i, sy = j;
if (grid[i][j] == 'H') bees.pb({i, j});
}
}
prepare();
int lo = 0, hi = 2000000;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (bfs(mid)) lo = mid;
else hi = mid - 1;
}
// bfs(2);
cout << lo - 1;
return 0;
}
