#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>
#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>
#define IO (std::string) ""
std::ifstream fin(IO + ".in");
std::ofstream fout(IO + ".out");
#define NMAX 1000
#define INF INT_MAX
int n, s;
char map[NMAX][NMAX];
pii start, finish;
std::vector<pii> hives;
std::vector<std::vector<int>> d1(NMAX, std::vector<int>(NMAX, INF)),
d2(NMAX, std::vector<int>(NMAX, INF));
int di[]{1, -1, 0, 0}, dj[]{0, 0, 1, -1};
void citire() {
std::cin >> n >> s;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
std::cin >> map[i][j];
if (map[i][j] == 'M')
start = {i, j};
if (map[i][j] == 'D')
finish = {i, j};
if (map[i][j] == 'H')
hives.push_back({i, j});
}
}
bool in(pii coord) {
int i = coord.first, j = coord.second;
return i >= 0 && i < n && j >= 0 && j < n;
}
void bfs(std::queue<pii> &q, std::vector<std::vector<int>> &d,
std::function<bool(pii coords)> check) {
while (!q.empty()) {
pii u = q.front();
int i = u.first;
int j = u.second;
q.pop();
for (int k = 0; k < 4; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (check({ni, nj}) && d[ni][nj] > d[i][j] + 1) {
d[ni][nj] = d[i][j] + 1;
q.push({ni, nj});
}
}
}
}
void bfs2(std::queue<pii> &q, std::vector<std::vector<int>> &d,
std::function<bool(pii coords)> check) {
while (!q.empty()) {
pii u = q.front();
int i = u.first;
int j = u.second;
q.pop();
for (int k = 0; k < 4; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (check({ni, nj}) && d[ni][nj] > d[i][j] + 1) {
if (d[i][j] + 1 < s * d2[ni][nj]) {
d[ni][nj] = d[i][j] + 1;
q.push({ni, nj});
}
}
}
}
}
int b_search(int l, int r, std::function<bool(int)> f) {
while (r > l + 1) {
int mid = (r + l) / 2;
if (f(mid))
l = mid;
else
r = mid;
}
return l;
}
int ok = 0;
int main() {
std::cin.tie(0)->std::ios::sync_with_stdio(0);
citire();
std::queue<pii> q;
for (pii it : hives) {
q.push(it);
d2[it.first][it.second] = 0;
}
bfs(q, d2, [&](pii coords) {
return in(coords) && map[coords.first][coords.second] != 'D' &&
map[coords.first][coords.second] != 'T';
});
int ans = b_search(0, n * n, [&](int w) {
std::vector<std::vector<int>> d(NMAX, std::vector<int>(NMAX, INF));
d[start.first][start.second] = w * s;
q.push(start);
if (w >= d2[start.first][start.second])
q.pop();
bfs2(q, d, [&](pii coords) {
return in(coords) && map[coords.first][coords.second] != 'H' &&
map[coords.first][coords.second] != 'T';
});
for (int k = 0; k < 4; k++) {
if (d[finish.first+di[k]][finish.second+dj[k]] != INF) {
ok = 1;
return true;
}
}
return false;
});
if (ok) {
std::cout << ans << '\n';
} else
std::cout << -1 << '\n';
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (d2[i][j] != INF)
std::cout << d2[i][j] << ' ';
else
std::cout << "oo ";
}
std::cout << '\n';
}*/
return 0;
}
