#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 805
#define mod 1000000007
char a[maxn][maxn];
int n, s, Bee_dist[maxn][maxn], Mecho_dist[maxn][maxn];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
vector<pair<int, int>> pos_hive;
pair<int, int> pos_home, pos_Mecho;
queue<pair<int, int>> Bee_q, Mecho_q;
bool Bee_inside(int x, int y) {
return (1 <= x && x <= n && 1 <= y && y <= n && a[x][y] != 'T' && a[x][y] != 'D');
}
bool Mecho_inside(int x, int y) {
return (1 <= x && x <= n && 1 <= y && y <= n && a[x][y] != 'T' && a[x][y] != 'H');
}
bool f(int time) {
memset(Bee_dist, 0x3f, sizeof Bee_dist);
memset(Mecho_dist, 0x3f, sizeof Mecho_dist);
for (auto [x, y] : pos_hive) {
Bee_q.push({x, y});
Bee_dist[x][y] = 0;
}
while (Bee_q.size()) {
auto [x, y] = Bee_q.front();
Bee_q.pop();
for (int dir = 0; dir < 4; dir += 1) {
int newx = x + dx[dir], newy = y + dy[dir];
if (Bee_inside(newx, newy) && Bee_dist[newx][newy] > Bee_dist[x][y] + 1) {
Bee_dist[newx][newy] = Bee_dist[x][y] + 1;
Bee_q.push({newx, newy});
}
}
}
Mecho_dist[pos_Mecho.first][pos_Mecho.second] = 0;
Mecho_q.push({pos_Mecho.first, pos_Mecho.second});
while (Mecho_q.size()) {
auto [x, y] = Mecho_q.front();
Mecho_q.pop();
if (Bee_dist[x][y] <= time) {
continue;
}
for (int dir = 0; dir < 4; dir += 1) {
int newx = x + dx[dir], newy = y + dy[dir];
if (Mecho_inside(newx, newy) && Mecho_dist[newx][newy] > Mecho_dist[x][y] + 1) {
if (Mecho_dist[x][y] + 1 < s * Bee_dist[newx][newy]) {
Mecho_dist[newx][newy] = Mecho_dist[x][y] + 1;
Mecho_q.push({newx, newy});
}
}
}
}
for (int dir = 0; dir < 4; dir += 1) {
int x = pos_home.first + dx[dir], y = pos_home.second + dy[dir];
if (Mecho_inside(x, y) && Mecho_dist[x][y] < 1e9) {
return true;
}
}
return false;
}
void solve() {
cin >> n >> s;
for (int i = 1; i <= n; i += 1) for (int j = 1; j <= n; j += 1) {
cin >> a[i][j];
if (a[i][j] == 'H') {
pos_hive.push_back({i, j});
}
else if (a[i][j] == 'M') {
pos_Mecho = {i, j};
}
else if (a[i][j] == 'D') {
pos_home = {i, j};
}
}
int l = -1, r = n * n + 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (f(m)) {
l = m;
}
else {
r = m;
}
}
cout << l - 1;
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int test_case = 1;
// cin >> test_case;
for (int i = 1; i <= test_case; i += 1) {
solve();
}
return 0;
}
