// https://oj.uz/problem/view/IOI09_mecho
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
// binary search + BFS + floodfill
// n <= 800, s <= 1000
int n, s;
char m[805][805];
int mr,mc,dr,dc;
struct E {
int r,c,d;
};
queue<E> q;
const int INF = 1e9;
int beetime[805][805]; // time for bees to reach here
int steps[805][805]; // min steps for mecho to reach here
// init q before calling this
void bfs(int dist[][805]) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = -1;
while (!q.empty()) {
E e = q.front();
q.pop();
if (e.r < 0 || e.r >= n || e.c < 0 || e.c >= n) continue;
if (m[e.r][e.c] == 'T' || dist[e.r][e.c] != -1) continue;
dist[e.r][e.c] = e.d;
q.push({e.r+1, e.c, e.d+1});
q.push({e.r-1, e.c, e.d+1});
q.push({e.r, e.c+1, e.d+1});
q.push({e.r, e.c-1, e.d+1});
}
}
// check if eating honey for t minutes is ok
bool check(int t) {
q.push({mr, mc, t*s});
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
steps[i][j] = -1;
while (!q.empty()) {
E e = q.front();
q.pop();
if (e.r < 0 || e.r >= n || e.c < 0 || e.c >= n) continue;
if (m[e.r][e.c] == 'T' || steps[e.r][e.c] != -1) continue;
if (e.d / s >= beetime[e.r][e.c]) continue; // stinged by bees
steps[e.r][e.c] = e.d;
q.push({e.r+1, e.c, e.d+1});
q.push({e.r-1, e.c, e.d+1});
q.push({e.r, e.c+1, e.d+1});
q.push({e.r, e.c-1, e.d+1});
}
return steps[dr][dc] != -1;
}
int main() {
scanf("%d %d", &n, &s);
for (int i = 0; i < n; i++) {
scanf("%s", m[i]);
for (int j = 0; j < n; j++)
if (m[i][j] == 'M') mr = i, mc = j;
else if (m[i][j] == 'D') dr = i, dc = j;
else if (m[i][j] == 'H') q.push({i,j,0});
}
bfs(beetime);
int lo = 0, hi = 2000;
while (lo < hi) {
int mid = (lo+hi+1) / 2;
if (check(mid))
lo = mid;
else
hi = mid-1;
}
if (lo == 0 && !check(0))
printf("-1");
else
printf("%d", lo);
return 0;
}
