/**
* 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 in_gird(int i, int j) {
return 0 <= i && i < n && 0 <= j && j < n && 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 (in_gird(i, j)) {
if (g[i][j] == 'D' or dist[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 (in_gird(x.i, x.j) && x.k >= 0) {
if (vis[x.i][x.j]) continue;
vis[x.i][x.j] = true;
if (g[x.i][x.j] == 'D') {
cout << x.k;
return 0;
}
if (x.cnt >= dist[x.i][x.j]*s) continue;
x.k = min(x.k, (dist[x.i][x.j]*s - x.cnt) / s - ((dist[x.i][x.j]*s - 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;
}
