#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MN=802;
int N, S, bee[MN][MN], best[MN][MN], dist[MN][MN];
char gr[MN][MN];
pii start, dest;
bool chk(int r, int c) {
return 0 <= r && r < N && 0 <= c && c < N && gr[r][c] != 'T' && gr[r][c] != 'H';
}
bool bschk(int wait) {
queue<pii> q;
q.emplace(start);
dist[start.first][start.second] = 0;
if(wait > bee[start.first][start.second]) return 0;
while(!q.empty()) {
int r = q.front().first, c = q.front().second;
q.pop();
int d = dist[r][c] + 1;
if(chk(r+1,c) && dist[r+1][c] == -1 && bee[r+1][c] - d/S - wait > -1) {
dist[r+1][c] = d;
q.emplace(r+1, c);
}
if(chk(r-1,c) && dist[r-1][c] == -1 && bee[r-1][c] - d/S - wait > -1) {
dist[r-1][c] = d;
q.emplace(r-1, c);
}
if(chk(r,c+1) && dist[r][c+1] == -1 && bee[r][c+1] - d/S - wait > -1) {
dist[r][c+1] = d;
q.emplace(r, c+1);
}
if(chk(r,c-1) && dist[r][c-1] == -1 && bee[r][c-1] - d/S - wait > -1) {
dist[r][c-1] = d;
q.emplace(r, c-1);
}
}
return dist[dest.first][dest.second] > -1;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin>>N>>S;
queue<pii> beeq;
for(int i=0; i<N; ++i) {
cin>>gr[i];
for(int j=0; j<N; ++j) {
if(gr[i][j] == 'H') beeq.emplace(i,j);
if(gr[i][j] == 'M') start = pii(i,j);
if(gr[i][j] == 'D') dest = pii(i,j);
}
}
memset(bee, -1, sizeof(bee));
while(!beeq.empty()) {
int r = beeq.front().first, c = beeq.front().second;
beeq.pop();
int dist = bee[r][c];
if(chk(r+1,c) && bee[r+1][c] == -1 && gr[r+1][c] != 'D') {
bee[r+1][c] = dist+1;
beeq.emplace(r+1, c);
}
if(chk(r-1,c) && bee[r-1][c] == -1 && gr[r-1][c] != 'D') {
bee[r-1][c] = dist+1;
beeq.emplace(r-1, c);
}
if(chk(r,c+1) && bee[r][c+1] == -1 && gr[r][c+1] != 'D') {
bee[r][c+1] = dist+1;
beeq.emplace(r, c+1);
}
if(chk(r,c-1) && bee[r][c-1] == -1 && gr[r][c-1] != 'D') {
bee[r][c-1] = dist+1;
beeq.emplace(r, c-1);
}
}
bee[dest.first][dest.second] = 1e9;
int lo = 0, hi = N*N, ans = -1;
while(lo <= hi) {
int mid = (lo+hi)/2;
memset(dist, -1, sizeof(dist));
if(bschk(mid)) {
ans = mid;
lo = mid+1;
} else hi = mid-1;
}
cout<<ans<<'\n';
return 0;
}
