#include <bits/stdc++.h>
using namespace std;
const int N = 800, M = 800;
int bear[N][M], bees[N][M];
string a[N];
int n, speed;
pair<int,int> dir[] = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};
bool valid(int i, int j) {
return 0 <= i && i < n && 0 <= j && j < n && a[i][j] != 'T';
}
void bfs(int dist[N][M], vector<pair<int,int>> s, bool bee) {
for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) dist[i][j] = INT_MAX;
queue<pair<int, int>> q;
for (auto [si, sj] : s) {
dist[si][sj] = 0;
q.emplace(si, sj);
}
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (auto [di, dj] : dir) {
int ni = i + di;
int nj = j + dj;
if (!valid(ni, nj)) continue;
if (bee && a[ni][nj] == 'D') continue;
if (dist[ni][nj] == INT_MAX) {
dist[ni][nj] = dist[i][j] + speed;
q.emplace(ni, nj);
}
}
}
}
int main() {
cin >> n >> speed;
int si, sj, ei, ej;
vector<pair<int,int>> hives;
for (int i = 0; i < n; i++) {
cin >> a[i];
for (int j = 0; j < n; j++) {
if (a[i][j] == 'M') si = i, sj = j;
if (a[i][j] == 'D') ei = i, ej = j;
if (a[i][j] == 'H') hives.emplace_back(i, j);
}
}
bfs(bees, hives, true);
auto check = [&](int minutes) {
memset(bear, -1, sizeof bear);
queue<pair<int,int>> q;
bear[si][sj] = minutes * speed;
if (bear[si][sj] > bees[si][sj])
return false;
q.emplace(si, sj);
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (auto [di, dj] : dir) {
int ni = i + di;
int nj = j + dj;
if (!valid(ni, nj)) continue;
int nd = bear[i][j] + 1;
if (-1 == bear[ni][nj] && nd <= bees[ni][nj]) {
bear[ni][nj] = nd;
q.emplace(ni, nj);
}
}
}
return bear[ei][ej] != -1;
};
int l = -1, r = n*n + 1;
while (r-l > 1) {
int mid = (l+r)/2;
(check(mid) ? l : r) = mid;
}
cout << l;
}
