// #include "myheader.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define int long long
// #define ll long long
#define pi pair<int, int>
#define ti tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
vector<vector<char>> grid;
vector<vector<ll>> t;
vector<pi> direction={{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n;
int s;
int si=-1, sj=-1, ei=-1, ej=-1;
bool bfs(int mid) {
vector<vector<int>> step(n, vector<int>(n, -1));
queue<pi> nq;
step[si][sj]=s*mid;
nq.push({si, sj});
while(nq.size()) {
auto [i, j]=nq.front(); nq.pop();
if(grid[i][j]=='D') return true;
for(auto &[di, dj]: direction) {
int ni=i+di;
int nj=j+dj;
if(ni>=0 && nj>=0 && ni<n && nj<n && (step[i][j]+1)<s*t[ni][nj] && grid[ni][nj]!='T' && step[ni][nj]==-1) {
step[ni][nj]=step[i][j]+1;
nq.push({ni, nj});
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
grid.resize(n, vector<char>(n));
t.resize(n, vector<int>(n, LLONG_MAX));
queue<pi> q;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin >> grid[i][j];
if(grid[i][j]=='H') {
q.push({i, j});
t[i][j]=0;
} else if(grid[i][j]=='M') {
si=i;
sj=j;
} else if(grid[i][j]=='D') {
ei=i;
ej=j;
}
}
}
while(q.size()) {
auto [i, j]=q.front(); q.pop();
for(auto &[di, dj]: direction) {
int ni=i+di;
int nj=j+dj;
if(ni>=0 && nj>=0 && ni<n && nj<n && t[ni][nj]==LLONG_MAX && (grid[ni][nj]!='T' && grid[ni][nj]!='D')) {
if(t[i][j] == LLONG_MAX) t[ni][nj] = 1;
else t[ni][nj]=t[i][j]+1;
q.push({ni, nj});
}
}
}
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < n ; j++) if (t[i][j] == 0) t[i][j] = LLONG_MAX;
}
int l=-1, r=INT_MAX;
while(l<r) {
int mid=(l+r+1)/2;
if(bfs(mid)) {
l=mid;
} else {
r=mid-1;
}
}
cout << l;
return 0;
}
