#include <bits/stdc++.h>
using namespace std;
int n,s;
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};
pii st ,ed;
bool check(int delay) {
auto [i,j] = st;
if (visbee[i][j] && bee[i][j] <= delay) return false;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
vismhee[i][j] = false;
mhee[i][j] = 0;
}
}
queue<pii> q;
q.push(st);
vismhee[i][j] = true;
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] || grid[ni][nj] == 'T') continue;
if (grid[ni][nj] == 'D') return true;
int mheet = delay + (mhee[i][j] + 1) / s;
if (!visbee[ni][nj] || mheet < bee[ni][nj]) {
mhee[ni][nj] = mhee[i][j] + 1;
vismhee[ni][nj] = true;
q.emplace(ni,nj);
}
}
}
return false;
}
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
queue<pii> b;
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') st = {i, j};
if (grid[i][j] == 'D') ed = {i, j};
}
}
while (!b.empty()) {
auto [i,j] = b.front();
b.pop();
for (int k=0; k<4; k++) {
int ni = i + di[k], nj = j + dj[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
if (visbee[ni][nj] || grid[ni][nj] == 'D' || grid[ni][nj] == 'T') continue;
bee[ni][nj] = bee[i][j] + 1;
visbee[ni][nj] = true;
b.emplace(ni,nj);
}
}
int l=0,r=n*n, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans;
}
