#include <iostream>
#include <vector>
#include <queue>
using namespace std;
constexpr int EMPTY = 0;
constexpr int BARRIER = 1;
constexpr int MECHO = 2;
constexpr int DANGER = 3;
constexpr int dx[] = { 0, 1, 0, -1 };
constexpr int dy[] = { 1, 0, -1, 0 };
inline bool test(
int N, int S, int wait, pair<int, int> start, pair<int, int> finish,
vector<pair<int, int>> trees, vector<pair<int, int>> hives
) {
vector<vector<int>> mat(N + 2, vector<int>(N + 2, 0));
queue<pair<int, int>> bees, pos;
for (int i = 0; i <= N + 1; ++i)
mat[i][0] = mat[0][i] = mat[i][N + 1] = mat[N + 1][i] = BARRIER;
for (const auto[x, y] : trees)
mat[x][y] = BARRIER;
for (const auto[x, y] : hives) {
mat[x][y] = DANGER;
bees.emplace(x, y);
}
mat[start.first][start.second] = MECHO;
pos.push(start);
for (int time = 1; !bees.empty() && !pos.empty(); ++time) {
if (time > wait) {
for (int step = 1; step <= S; ++step) {
const int sz = pos.size();
for (int i = 0; i < sz; ++i) {
const auto[x0, y0] = pos.front();
pos.pop();
for (int j = 0; j < 4; ++j) {
const int x1 = x0 + dx[j];
const int y1 = y0 + dy[j];
if (mat[x1][y1] == EMPTY) {
mat[x1][y1] = MECHO;
pos.emplace(x1, y1);
}
}
}
}
}
const int sz = bees.size();
for (int i = 0; i < sz; ++i) {
const auto[x0, y0] = bees.front();
bees.pop();
for (int j = 0; j < 4; ++j) {
const int x1 = x0 + dx[j];
const int y1 = y0 + dy[j];
if (mat[x1][y1] == EMPTY || mat[x1][y1] == MECHO) {
mat[x1][y1] = DANGER;
bees.emplace(x1, y1);
}
}
}
if (mat[finish.first][finish.second] == MECHO)
return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<pair<int, int>> trees, hives;
pair<int, int> start, finish;
int N, S;
char ch;
cin >> N >> S;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
cin >> ch;
if (ch == 'T')
trees.emplace_back(i, j);
else if (ch == 'H')
hives.emplace_back(i, j);
else if (ch == 'M')
start = { i, j };
else if (ch == 'D')
finish = { i, j };
}
}
int l = 0, r = N * N, ans = -1;
while (l <= r) {
const int mid = (l + r) >> 1;
if (test(N, S, mid, start, finish, trees, hives)) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
cout << ans;
return 0;
}
