#include <bits/stdc++.h>
using namespace std;
bool visited[805][805];
int distBee[805][805];
int distBear[805][805];
char g[805][805];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int n,s,sr,sc,er,ec,mxtime;
bool possible(int t) {
memset(visited,0,sizeof visited);
queue < pair <pair<int,int>,int> > bfs;
bfs.push({{sr,sc},0});
visited[sr][sc] = true;
distBear[sr][sc] = t;
if (distBear[sr][sc]>=distBee[sr][sc]) return false;
while (!bfs.empty()) {
int curR = bfs.front().first.first;
int curC = bfs.front().first.second;
int steps = bfs.front().second;
bfs.pop();
for (int i=0;i<4;i++) {
int nr = curR + dr[i];
int nc = curC + dc[i];
if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T'||distBear[curR][curC]+((steps+1)%s==0?1:0)>=distBee[nr][nc]) continue;
visited[nr][nc] = true;
distBear[nr][nc] = distBear[curR][curC] + ((steps+1)%s==0?1:0);
bfs.push({{nr,nc},steps+1});
}
}
if (visited[er][ec]) return true;
return false;
}
int main() {
queue < pair<int,int> > bfs;
cin >> n >> s;
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
cin >> g[i][j];
distBee[i][j]=1000000;
if (g[i][j]=='M') sr = i,sc = j;
else if (g[i][j]=='D') er = i,ec = j;
else if (g[i][j]=='H') {
visited[i][j] = true;
distBee[i][j] = 0;
bfs.push({i,j});
}
}
}
while (!bfs.empty()) {
int curR = bfs.front().first;
int curC = bfs.front().second;
bfs.pop();
for (int i=0;i<4;i++) {
int nr = curR + dr[i];
int nc = curC + dc[i];
if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T'||g[nr][nc]=='D') continue;
visited[nr][nc] = true;
distBee[nr][nc] = distBee[curR][curC]+1;
mxtime = max(mxtime,distBee[nr][nc]);
bfs.push({nr,nc});
}
}
int lo = 0,hi = mxtime;
while (lo<hi) {
int mid = (lo+hi+1)/2;
bool poss = possible(mid);
if (poss) lo = mid;
else hi = mid-1;
}
if (!possible(0)) cout << -1 << endl;
else cout << lo << endl;
return 0;
}
