#include <bits/stdc++.h>
using namespace std;
int bee[810][810];
bool visbee[810][810];
int mhee[810][810];
bool vismhee[810][810];
string grid[810];
typedef pair<int,int> pii;
int di[] = {0,0,1,-1};
int dj[] = {1,-1,0,0};
queue<pii> q,b;
pii home;
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,s; cin >> n >> s;
for (int i=0;i<n;i++) {
cin >> grid[i];
for (int j=0;j<n;j++) {
if (grid[i][j] == 'H') {
b.emplace(i,j);
bee[i][j] = 0;
visbee[i][j] = true;
}
if (grid[i][j] == 'M') {
q.emplace(i,j);
mhee[i][j] = 0;
vismhee[i][j] = true;
}
}
}
while (!b.empty()) {
auto [i,j] = b.front();
b.pop();
for (int k=0;k<4;k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
if (visbee[ni][nj]) continue;
if (grid[ni][nj] == 'D' || grid[ni][nj] == 'T') continue;
bee[ni][nj] = bee[i][j] + 1;
visbee[ni][nj] = true;
b.emplace(ni,nj);
}
}
while (!q.empty()) {
auto [i,j] = q.front();
q.pop();
for (int k=0;k<4;k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
if (vismhee[ni][nj]) continue;
if (grid[ni][nj] == 'T' || (visbee[ni][nj] && bee[ni][nj] <= ((mhee[i][j]+1)/s))) continue;
mhee[ni][nj] = mhee[i][j] + 1;
if (grid[ni][nj] == 'D') {
home = {ni,nj};
vismhee[ni][nj] = true;
while (!q.empty()) q.pop();
break;
}
vismhee[ni][nj] = true;
q.emplace(ni,nj);
}
}
auto[i,j] = home;
cout << bee[i][j] - (mhee[i][j]/s)-1;
}
