#include <bits/stdc++.h>
#define nl '\n'
#define int long long
using namespace std;
int n, s;
array<int, 2> starting, ending;
bool bfs(int t, vector< vector<bool> >& vis, vector< vector<char> >& v, vector< vector<int> >& obstacle){
bool ans = 0;
queue< array<int, 3> > q;
q.push({starting[0], starting[1], t*s});
while(!q.empty()){
auto top = q.front(); q.pop();
int i = top[0];
int j = top[1];
int currTime = top[2];
if(i <= -1 || i >= n || j <= -1 || j >= n) continue;
if(vis[i][j] || v[i][j] == 'T' || obstacle[i][j] <= currTime) continue;
vis[i][j] = 1;
if(v[i][j] == 'D') ans = 1;
q.push({i-1, j, currTime+1});
q.push({i, j-1, currTime+1});
q.push({i+1, j, currTime+1});
q.push({i, j+1, currTime+1});
}
return ans;
}
void solve(){
cin >> n >> s;
vector< vector<char> > v(n, vector<char>(n));
queue< array<int, 3> > q; // [0] = i, [1] = j, [2] = time
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> v[i][j];
if(v[i][j] == 'H') q.push({i, j, 0});
if(v[i][j] == 'M') starting = {i, j};
if(v[i][j] == 'D') ending = {i, j};
}
}
vector< vector<int> > obstacle(n, vector<int>(n, 1e9));
vector< vector<bool> > visB(n, vector<bool>(n, 0));
while(!q.empty()){
auto top = q.front(); q.pop();
int i = top[0];
int j = top[1];
int t = top[2];
if(i <= -1 || i >= n || j <= -1 || j >= n) continue;
if(visB[i][j] || v[i][j] == 'T' || v[i][j] == 'D') continue;
visB[i][j] = 1;
obstacle[i][j] = t*s;
q.push({i-1, j, t+1});
q.push({i, j-1, t+1});
q.push({i+1, j, t+1});
q.push({i, j+1, t+1});
}
int lo = 0;
int hi = 1e11;
int ans = INT_MAX;
while(lo <= hi){
int mid = lo+(hi-lo)/2;
vector< vector<bool> > vis(n, vector<bool>(n, 0));
if(bfs(mid, vis, v, obstacle)){
ans = mid;
lo = mid+1;
} else {
hi = mid-1;
}
}
cout << (ans == INT_MAX ? -1 : ans) << nl;
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t = 1; /*cin >> t;*/ while(t--) solve();
}
