#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define sz(v) (int)v.size()
#define fi first
#define se second
#define ALL(A) A.begin(), A.end()
#define compact(v) v.erase(unique(ALL(v)), end(v))
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define BIT(mask,i) ((mask>>(i))&1)
#define MASK(a) (1LL << (a))
#define lwb lower_bound
#define upb upper_bound
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vpi = vector<pii>;
using vpl = vector<pll>;
const int dx[] = {0, 0, 1, - 1};
const int dy[] = {- 1, 1, 0, 0};
int n, S;
char a[805][805];
ll dist[805][805];
ll f[805][805];
int sx, sy, fx, fy;
bool check(int T){
FOR(i, 1, n) FOR(j, 1, n){
f[i][j] = 1e18;
}
if(dist[sx][sy] <= T * S) return 0;
queue <pair <int, int>> que;
f[sx][sy] = 1LL * T * S;
que.push({sx, sy});
while(!que.empty()){
int u = que.front().fi, v = que.front().se;
que.pop();
FOR(s, 0, 3){
int x = u + dx[s], y = v + dy[s];
if(x < 1 || x > n || y < 1 || y > n || a[x][y] == 'T') continue;
if (x == fx && y == fy) return true;
ll t = (f[u][v] + 1) / S;
if(t >= dist[x][y] / S) continue;
if(minimize(f[x][y], f[u][v] + 1)){
que.push({x, y});
}
}
}
return (f[fx][fy] < 1e18);
}
void solve(){
cin >> n >> S;
FOR(i, 1, n) FOR(j, 1, n){
cin >> a[i][j];
if(a[i][j] == 'D'){
fx = i;
fy = j;
}
if(a[i][j] == 'M'){
sx = i;
sy = j;
}
}
if(fx == 0 && fy == 0){
cout << - 1;
return;
}
#define bg array <ll, 3>
priority_queue <bg, vector <bg>, greater <bg>> pq;
FOR(i, 1, n) FOR(j, 1, n){
dist[i][j] = 1e18;
if(a[i][j] == 'H'){
dist[i][j] = 0;
pq.push({0, i, j});
}
}
while(!pq.empty()){
ll cost = pq.top()[0];
int u = pq.top()[1], v = pq.top()[2];
pq.pop();
if(cost > dist[u][v]) continue;
FOR(s, 0, 3){
int x = u + dx[s], y = v + dy[s];
if(x < 1 || x > n || y < 1 || y > n || a[x][y] == 'T') continue;
if(minimize(dist[x][y], dist[u][v] + S)){
pq.push({dist[x][y], x, y});
}
}
}
int l = 0, r = n * n, ans = - 1;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans;
}
int main(void){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1; // cin >> tc;
while (tc--) solve();
return 0;
}
