#include <bits/stdc++.h>
using namespace std;
#define N 805
#define fi first
#define se second
typedef pair<int, int> ii;
int n, d[N][N], d1[N][N], xs, ys, xe, ye, s;
vector<ii> o;
char a[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool in(int u, int v){
return u >= 1 && u <= n && v >= 1 && v <= n && a[u][v] != 'T';
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
queue<ii> q;
cin >> n >> s;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
d1[i][j] = d[i][j] = 1e9;
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
cin >> a[i][j];
if (a[i][j] == 'H') {
d1[i][j] = 0;
q.push({i, j});
}
if (a[i][j] == 'D'){
xe = i;
ye = j;
}
if (a[i][j] == 'M'){
xs = i;
ys = j;
}
}
}
while (!q.empty()){
int u = q.front().fi;
int v = q.front().se;
q.pop();
for (int i = 0; i <= 3; i++){
int newu = u + dx[i];
int newv = v + dy[i];
if (!in(newu, newv)) continue;
if (newu == xe && newv == ye) continue;
if (d1[newu][newv] > d1[u][v] + 1){
d1[newu][newv] = d1[u][v] + 1;
q.push({newu, newv});
}
}
}
int l = 1, r = n * n, rt = -1;
while (l <= r){
int mid = (l + r) >> 1;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) d[i][j] = 1e9;
}
d[xs][ys] = 0;
q.push({xs, ys});
while (!q.empty()){
int u = q.front().fi;
int v = q.front().se;
q.pop();
for (int i = 0; i <= 3; i++){
int newu = u + dx[i];
int newv = v + dy[i];
if (!in(newu, newv)) continue;
int newd = mid + (d[u][v] + 1) / s;
if (d1[newu][newv] <= newd) continue;
if (d[newu][newv] > d[u][v] + 1){
d[newu][newv] = d[u][v] + 1;
q.push({newu, newv});
}
}
}
if (d[xe][ye] != 1e9) {rt = mid; l = mid + 1;}
else r = mid - 1;
}
cout << rt;
return 0;
}
