#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f1 first
#define s2 second
using ii = pair<int, int>;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int MAX = 869;
const int inf = 1e9 + 69;
int N, S;
char s[MAX][MAX];
int dist[MAX][MAX];
inline bool valid(int r, int c)
{
return 0 <= r && r <= N && 0 <= c && c < N;
}
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> S;
for (int i = 0; i < N; ++i)
cin >> s[i];
ii st, fn;
vector<ii> bee;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (s[i][j] == 'M')
st = {i, j};
else if (s[i][j] == 'H')
bee.pb({i, j});
else if (s[i][j] == 'D')
fn = {i, j};
}
}
const auto check = [&](int val) -> bool
{
queue<ii> q, qb; //bear, bee
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
dist[i][j] = -inf;
const auto bearMove = [&]() -> bool
{
while (!q.empty() && dist[q.front().f1][q.front().s2] < 0)
q.pop();
if (q.empty())
return false;
bool moved = false;
int cur = dist[q.front().f1][q.front().s2];
while (!q.empty())
{
auto [r, c] = q.front();
if (dist[r][c] >= cur + S)
break;
q.pop();
if (dist[r][c] < 0)
continue;
for (int i = 0; i < 4; ++i)
{
int nr = r + dx[i], nc = c + dy[i];
if (valid(nr, nc) && s[nr][nc] != 'T' && (dist[nr][nc] == -inf))
moved = true, dist[nr][nc] = dist[r][c] + 1, q.push({nr, nc});
}
}
return moved;
};
const auto beeSwarm = [&]() -> void
{
if (qb.empty())
return;
int cur = dist[qb.front().f1][qb.front().s2];
while (!qb.empty())
{
auto [r, c] = qb.front();
if (dist[r][c] != cur)
break;
qb.pop();
for (int i = 0; i < 4; ++i)
{
int nr = r + dx[i], nc = c + dy[i];
if (valid(nr, nc) && s[nr][nc] != 'T' && s[nr][nc] != 'D' && (dist[nr][nc] == -inf || dist[nr][nc] >= 0))
dist[nr][nc] = dist[r][c] - 1, qb.push({nr, nc});
}
}
};
dist[st.f1][st.s2] = 0;
q.push(st);
for (auto [r, c] : bee)
dist[r][c] = -1, qb.push({r, c});
for (int rep = 0; rep < val; ++rep)
beeSwarm();
while (dist[fn.f1][fn.s2] == -inf)
{
if (!bearMove())
return false;
beeSwarm();
// for (int i = 0; i < N; ++i)
// for (int j = 0; j < N; ++j)
// cerr << setw(2) << max(-9, dist[i][j]) << " \n"[j == N-1];
}
return true;
};
int l = -1, r = N*N;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
return 0;
}
