#include <bits/stdc++.h>
using namespace std;
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, -1, 1};
typedef pair<int, int> pii;
#define ff first
#define ss second
const int mxn = 808;
char mp[mxn][mxn];
bool vs[mxn][mxn];
int bee[mxn][mxn];
int n, s, Si, Sj, Di, Dj;
bool can(int i, int j) {
if(mp[i][j] == 'T') return false;
if(mp[i][j] == 'H') return false;
return true;
}
bool bfs(int M) {
priority_queue<pair<int, pii>> pq;
pq.push({0, {Si, Sj}});
memset(vs, 0, sizeof vs);
vs[Si][Sj] = true;
while(pq.size()) {
int k = -pq.top().ff;
int i = pq.top().ss.ff;
int j = pq.top().ss.ss;
pq.pop();
if(i == Di && j == Dj) return true;
int minute = k / s;
if(minute + M >= bee[i][j]) continue;
// cout << minute << ": (" << k << ") " << i << ' ' << j << " - " << bee[i][j] << '\n';
for(int t = 0; t < 4; t++) {
int I = i + di[t];
int J = j + dj[t];
if(!vs[I][J] && can(I, J)) {
vs[I][J] = 1;
pq.push({-(k + 1), {I, J}});
// cout << " > " << I << ' ' << J << '\n';
}
}
}
return false;
}
priority_queue<pair<int, pii>> pq;
void beefs() {
memset(bee, -1, sizeof bee);
while(pq.size()) {
int k = -pq.top().ff;
int i = pq.top().ss.ff;
int j = pq.top().ss.ss;
pq.pop();
bee[i][j] = k;
for(int t = 0; t < 4; t++) {
int I = i + di[t];
int J = j + dj[t];
if(!vs[I][J] && mp[I][J] != 'T' && mp[I][J] != 'D') {
vs[I][J] = true;
pq.push({-(k + 1), {I, J}});
}
}
}
}
int main() {
cin >> n >> s;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
cin >> mp[i][j];
if(mp[i][j] == 'H') {
pq.push({0, {i, j}});
vs[i][j] = true;
}
if(mp[i][j] == 'M') {
Si = i;
Sj = j;
}
if(mp[i][j] == 'D') {
Di = i;
Dj = j;
}
}
for(int i = 0; i <= n + 1; i++)
mp[i][0] = mp[i][n + 1] = mp[0][i] = mp[n + 1][i] = 'T';
beefs();
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++)
// cout << mp[i][j] << ' ';
// cout << '\n';
// }
if(!bfs(0)) {
cout << -1 << '\n';
return 0;
}
int L = 0, R = n * n + 1;
while(R - L > 1) {
int M = (L + R) / 2;
// cout << L << ' ' << R << ": " << M << '\n';
if(bfs(M)) L = M;
else R = M;
}
cout << L << '\n';
return 0;
}
