#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n';
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
int n, s;
char grid[800][800];
int dist[800][800];
int path[800][800];
vector<pair<int, int>> hives;
pair<int, int> start;
pair<int, int> home;
bool inside(int i, int j) {
if (i >= 0 && i < n && j >= 0 && j < n) {
return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
dist[i][j] = 1e9;
cin >> grid[i][j];
if (grid[i][j] == 'H') {
hives.push_back({i, j});
} else if (grid[i][j] == 'M') {
start = {i, j};
} else if (grid[i][j] == 'D') {
home = {i, j};
}
}
}
queue<pair<int, int>> q;
for (auto x : hives) {
q.push(x);
dist[x.first][x.second] = 0;
}
while (!q.empty()) {
pair<int, int> s = q.front();
q.pop();
for (int i = 0;i < 4;i++) {
if (inside(s.first + dx[i], s.second + dy[i])) {
if (dist[s.first + dx[i]][s.second + dy[i]] == 1e9 && grid[s.first + dx[i]][s.second + dy[i]] != 'T' && grid[s.first + dx[i]][s.second + dy[i]] != 'D') {
q.push({s.first + dx[i], s.second + dy[i]});
dist[s.first + dx[i]][s.second + dy[i]] = dist[s.first][s.second] + 1;
}
}
}
}
int l = 0;
int r = dist[start.first][start.second]-1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
path[i][j] = 1e9;
}
}
while (l <= r) {
int m = (l+r+1)/2;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
path[i][j] = 1e9;
}
}
queue<pair<int, int>> q;
q.push(start);
path[start.first][start.second] = 0;
while (!q.empty()) {
pair<int, int> t = q.front();
q.pop();
for (int i = 0;i < 4;i++) {
if (inside(t.first+dx[i], t.second+dy[i])) {
if (grid[t.first+dx[i]][t.second+dy[i]] != 'T' && grid[t.first+dx[i]][t.second+dy[i]] != 'H' && (dist[t.first+dx[i]][t.second+dy[i]]-m) > (path[t.first][t.second] + 1)/s) {
if (path[t.first+dx[i]][t.second+dy[i]] > path[t.first][t.second] + 1) {
q.push({t.first+dx[i], t.second+dy[i]});
path[t.first+dx[i]][t.second+dy[i]] = path[t.first][t.second] + 1;
}
}
}
}
}
if (path[home.first][home.second] != 1e9) {
l = m;
} else {
r = m-1;
}
if (m == 0 || (r == l && r != 0)) {
break;
}
}
if (l == 0 && path[home.first][home.second] == 1e9) {
cout << -1 << endl;
return 0;
}
cout << l << endl;
}
