#include <bits/stdc++.h>
using namespace std;
#define int long long
#define el '\n'
#define all(x) begin(x), end(x)
#define sz(s) (int)(s.size())
inline void setIO(string s) {
if(fopen((s + ".in").c_str(), "r")){
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
}
const int MOD = 1e9+7; //998244353;
const int N = 800 + 36;
char a[N][N];
int n, s;
int dx[4] = {-1, 0, 1, 0},
dy[4] = {0, 1, 0, -1};
int bee[N][N], dist[N][N];
pair<int, int> st, ed;
inline bool inside(int x, int y){
return x >= 1 && x<=n && y>=1 && y <= n;
}
void bfs(queue<pair<int, int>> &q){
while(sz(q)){
auto [x, y] = q.front(); q.pop();
for(int k=0; k<4; k++){
int nx = x + dx[k];
int ny = y + dy[k];
if(inside(nx, ny) && (a[nx][ny] != 'T' && a[nx][ny] != 'D') && bee[nx][ny] == -1){
bee[nx][ny] = bee[x][y] + 1;
q.push({nx, ny});
}
}
}
}
bool check(int t){
memset(dist, -1, sizeof dist);
queue<pair<int, int>> q;
q.push(st);
dist[st.first][st.second] = 0;
while(sz(q)){
auto [x, y] = q.front(); q.pop();
for(int k=0; k<4; k++){
int nx = x + dx[k];
int ny = y + dy[k];
int nd = dist[x][y] + 1;
if(inside(nx, ny) && (a[nx][ny] != 'T' && a[nx][ny] != 'H') && dist[nx][ny] == -1){
if(make_pair(nx, ny) == ed) return true;
if(t + nd/s < bee[nx][ny]){
dist[nx][ny] = nd;
q.push({nx, ny});
}
}
}
}
return false;
}
void Solve(){
memset(bee, -1, sizeof bee);
cin>> n>> s;
queue<pair<int, int>> q;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin>> a[i][j];
if(a[i][j] == 'H'){
bee[i][j] = 0;
q.push({i, j});
}
else if(a[i][j] == 'M') st = {i, j};
else if(a[i][j] == 'D') ed = {i, j};
}
}
bfs(q);
int l = 0, r = bee[st.first][st.second]-1;
int ans = -1;
while(l <= r){
int mid = l+r>>1;
if(check(mid)){
ans = mid;
l = mid+1;
}
else r = mid-1;
}
cout<< ans<<el;
}
signed main (){
setIO("Rem");
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T(1);
// cin >> T;
while(T--) Solve();
return 0;
}
