#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
int movex[4] = {-1, 0, 1, 0};
int movey[4] = {0, 1, 0, -1};
char maps[805][805];
int beeStep[805][805], meStep[805][805], n, Mx, My, s, Dx, Dy;
queue <pair <int, int> > bee, me;
inline bool check(int x, int y) {
if(x >= 0 && x < n && y >= 0 && y < n) return true;
return false;
}
inline bool can(int mid) {
int curx, cury, curstep, i, i1, movexx, moveyy;
memset(meStep, -1, sizeof(meStep));
me.push(mp(Mx * 1000 + My, mid));
while(!me.empty()) {
curx = me.front().F / 1000;
cury = me.front().F % 1000;
curstep = me.front().S;
me.pop();
if(meStep[curx][cury] == -1) {
meStep[curx][cury] = curstep;
if(maps[curx][cury] == 'D') break;
for(i = 0; i < 4; i++) {
for(i1 = 1; i1 <= s; i1++) {
movexx = movex[i] * i1 + curx;
moveyy = movey[i] * i1 + cury;
if(check(movexx, moveyy) && maps[movexx][moveyy] != 'T' && meStep[movexx][moveyy] == -1) {
if(beeStep[movexx][moveyy] != -1 && beeStep[movexx][moveyy] <= curstep) break;
me.push(mp(movexx * 1000 + moveyy, curstep + 1));
}
else break;
}
}
}
}
while(!me.empty())
me.pop();
if(beeStep[Dx][Dy] == -1) beeStep[Dx][Dy] = 1e9;
if(meStep[Dx][Dy] == -1) return false;
return meStep[Dx][Dy] < beeStep[Dx][Dy];
}
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio;
int i, j, l, r, curx, cury, curstep, movexx, moveyy, mid;
cin >> n >> s;
for(i = 0; i < n; i++) {
cin >> maps[i];
for(j = 0; j < n; j++) {
if(maps[i][j] == 'H')
bee.push(mp(i * 1000 + j, 0));
if(maps[i][j] == 'M') {
Mx = i; My = j;
}
if(maps[i][j] == 'D') {
Dx = i; Dy = j;
}
}
}
memset(beeStep, -1, sizeof(beeStep));
while(!bee.empty()) {
curx = bee.front().F / 1000;
cury = bee.front().F % 1000;
curstep = bee.front().S;
bee.pop();
if(beeStep[curx][cury] == -1) {
beeStep[curx][cury] = curstep;
for(i = 0; i < 4; i++) {
movexx = movex[i] + curx;
moveyy = movey[i] + cury;
if(check(movexx, moveyy) && maps[movexx][moveyy] != 'T' && beeStep[movexx][moveyy] == -1)
bee.push(mp(movexx * 1000 + moveyy, curstep + 1));
}
}
}
if(!can(0)) {
cout << "-1\n";
return 0;
}
l = 0; r = n * n;
while(l + 1 < r) {
mid = (l + r) / 2;
if(can(mid)) l = mid;
else r = mid;
}
cout << l << "\n";
return 0;
}
