#include <bits/stdc++.h>
using namespace std;
int r_c[]{0, 1, 0, -1};
int c_c[]{1, 0, -1, 0};
int n, s;
vector<vector<int>> arr;
int r_s, c_s;
int r_f, c_f;
queue<pair<int, int>> hives;
vector<vector<int>> dis;
void fill() {
while (hives.size() != 0) {
pair<int, int> t = hives.front();
for (int i = 0; i < 4; i++) {
int n_r = t.first + r_c[i];
int n_c = t.second + c_c[i];
if (min(n_r, n_c) >= 0 && max(n_r, n_c) < n) {
if (arr[n_r][n_c] == 0 && dis[n_r][n_c] == -1) {
dis[n_r][n_c] = dis[t.first][t.second] + 1;
hives.push({n_r, n_c});
}
}
}
hives.pop();
}
}
bool check(int time) {
vector<vector<int>> len(n, vector<int>(n));
queue<pair<int, int>> q;
q.push({r_s, c_s});
while (q.size() != 0) {
pair<int, int> t = q.front();
for (int i = 0; i < 4; i++) {
int n_r = t.first + r_c[i];
int n_c = t.second + c_c[i];
if (min(n_r, n_c) >= 0 && max(n_r, n_c) < n) {
if (arr[n_r][n_c] != -1 && len[n_r][n_c] == 0) {
if (dis[n_r][n_c] == -1 || (1 + len[t.first][t.second]) / s + time < dis[n_r][n_c]) {
len[n_r][n_c] = 1 + len[t.first][t.second];
q.push({n_r, n_c});
}
}
}
}
q.pop();
}
if (len[r_f][c_f] != 0) {
return true;
} else {
return false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
arr.resize(n, vector<int>(n));
dis.resize(n, vector<int>(n, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char c;
cin >> c;
if (c == 'T') {
arr[i][j] = -1;
} else if (c == 'M') {
r_s = i; c_s = j;
} else if (c == 'D') {
arr[i][j] = 1;
r_f = i; c_f = j;
} else if (c == 'H') {
dis[i][j] = 0;
hives.push({i, j});
}
}
}
fill();
if (!check(0)) {
cout << "-1\n";
} else {
int l = 0;
int r = dis[r_s][c_s];
while (r > l + 1) {
int m = (l + r) / 2;
if (check(m)) {
l = m;
} else {
r = m;
}
}
cout << l << "\n";
}
}
