#include "bits/stdc++.h"
using namespace std;
#define ii pair<int,int>
#define iii tuple<int,int,int>
const int ms = 8e2 + 5;
char grid[ms][ms];
bool bees[ms][ms], mecho[ms][ms];
int n, s;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
ii start, fim;
vector<ii> hives;
void step(queue<ii> &q){
queue<ii> nq;
while(!q.empty()){
int x, y;
tie(x, y) = q.front();
q.pop();
if(bees[x][y]) continue;
for(int i=0; i<4; i++){
int a = x +dx[i], b = y + dy[i];
if(a < 0 || a>= n || b < 0 || b>=n || bees[a][b] || grid[a][b] == 'T' ) continue;
if(!mecho[a][b]){
mecho[a][b] = true;
nq.push({a, b});
}
}
}
nq.swap(q);
}
void step_bees(queue<ii> &h){
queue<ii> new_h;
while(!h.empty()){
int x, y;
tie(x, y) = h.front();
h.pop();
for(int i=0; i<4; i++){
int a = x+dx[i], b = y+dy[i];
if(a < 0 || a >= n || b <0 || b >=n || grid[a][b] == 'T' || grid[a][b] == 'D') continue;
if(!bees[a][b]){
bees[a][b] = true;
new_h.push({a, b});
}
}
}
new_h.swap(h);
}
bool test(int mid){
memset(bees, 0, sizeof bees);
memset(mecho, 0, sizeof mecho);
queue<ii> h, m;
mecho[start.first][start.second] = true;
m.push(start);
for(int i=0; i<hives.size(); i++) {
bees[hives[i].first][hives[i].second] = true;
h.push(hives[i]);
}
for(int i=0; i<mid; i++) step_bees(h);
while(!m.empty()){
for(int i=0; i<s; i++)step(m);
step_bees(h);
}
return mecho[fim.first][fim.second];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> grid[i][j];
if(grid[i][j] == 'M') start ={i, j};
if(grid[i][j] == 'D') fim = {i, j};
if(grid[i][j] == 'H') hives.push_back({i, j});
}
}
int l=0, r = n*n;
int ans = -1;
while(l <= r){
int mid = (l+r)/2;
if(test(mid)){
ans = mid;
l = mid+1;
}
else r = mid -1;
}
// test(2);
cout << ans << '\n';
return 0;
}
