/**
* author : Lăng Trọng Đạt
* created: 2023-08-22
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int int64_t
#define mp make_pair
#define pb push_back
using pii = pair<int, int>;
const int MAXN = 800 + 5;
int dist[MAXN][MAXN];
char g[MAXN][MAXN];
bool vis[MAXN][MAXN];
int x_change[]{1, -1, 0, 0};
int y_change[]{0, 0, 1, -1};
int n, s;
struct Data {
int i, j, cnt, k;
// cnt: number of step, k: : the maximum possible number of minutes that Mecho can continue eating honey at his initial location, while still being able to get home safely.
// @return number of minutes passed
int t() {
return cnt / s;
}
};
bool vaild1(int i, int j, int d) {
return 0 <= i && i < n && 0 <= j && j < n &&
d < dist[i][j] && g[i][j] != 'T' && g[i][j] != 'D';
}
bool vaild2(int i, int j, int d) {
return 0 <= i && i < n && 0 <= j && j < n &&
!vis[i][j] && d < dist[i][j] && g[i][j] != 'T';
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("hi.inp", "r")) {
freopen("hi.inp", "r", stdin);
// freopen("hi.out", "w", stdout);
}
cin >> n >> s;
queue<pair<pii, int>> q;
queue<Data> q2;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> g[i][j];
if (g[i][j] == 'H') {
q.push({{i, j}, 0});
} else if (g[i][j] == 'M') {
q2.push({i, j, 0, n*n});
}
}
memset(dist, 0x3f3f3f, sizeof(dist));
while (q.size()) {
auto[p, d] = q.front(); q.pop();
auto[i, j] = p;
if (vaild1(i, j, d)) {
if (g[i][j] == 'D') continue;
dist[i][j] = d;
for (int k = 0; k < 4; k++) {
q.push({{i + x_change[k], j + y_change[k]}, d + 1});
}
}
}
while (q2.size()) {
Data x = q2.front(); q2.pop();
if (vaild2(x.i, x.j, x.t()) && x.k >= 0) {
vis[x.i][x.j] = true;
if (g[x.i][x.j] == 'D') {
cout << x.k;
return 0;
}
if (x.cnt % s == 0 && x.t() == dist[x.i][x.j]) continue;
x.k = min(x.k, dist[x.i][x.j] - x.t() - (x.cnt % s != 0));
db(x.i, x.j, x.k, x.t(), x.cnt, dist[x.i][x.j])
for (int k = 0; k < 4; k++) {
q2.push({x.i + x_change[k], x.j + y_change[k], x.cnt + 1, x.k});
}
}
}
cout << -1;
}
