#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair <int,int>
const int N=805;
const int INF=1e18; // ใช้ค่าที่เหมาะสม
const int dy[]={-1,1,0,0};
const int dx[]={0,0,-1,1};
int n, m, d_b[N][N], d_m[N][N];
pii st, en;
char c[N][N];
bool ok(int y, int x) {
return (y >= 1 && y <= n && x >= 1 && x <= n);
}
bool check(int mid) {
// 1. เช็คว่าผึ้งกินจุดเริ่มต้นไปหรือยังก่อนเริ่มเดิน
if (mid * m >= d_b[st.first][st.second]) return false;
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) d_m[i][j] = -1;
queue<pii> q;
q.push(st);
d_m[st.first][st.second] = mid * m;
while(!q.empty()){
auto [y, x] = q.front();
q.pop();
if (y == en.first && x == en.second) return true;
for(int i=0; i<4; i++){
int yy = y + dy[i], xx = x + dx[i];
if(!ok(yy, xx) || c[yy][xx] == 'T' || c[yy][xx] == 'H' || d_m[yy][xx] != -1) continue;
// 2. เงื่อนไขสำคัญ: ถ้าเป็นบ้าน (D) ไม่ต้องเช็ค d_b เพราะผึ้งเข้าไม่ได้
if (c[yy][xx] != 'D' && d_m[y][x] + 1 >= d_b[yy][xx]) continue;
d_m[yy][xx] = d_m[y][x] + 1;
q.push({yy, xx});
}
}
return false;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
queue<pii> q_b;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
d_b[i][j] = INF;
cin >> c[i][j];
if(c[i][j] == 'H') {
d_b[i][j] = 0;
q_b.push({i, j});
} else if(c[i][j] == 'M') st = {i, j};
else if(c[i][j] == 'D') en = {i, j};
}
}
// ผึ้งเดินกระจายทั่วแผนที่
while(!q_b.empty()){
auto [y, x] = q_b.front();
q_b.pop();
for(int i=0; i<4; i++){
int yy = y + dy[i], xx = x + dx[i];
// ผึ้งไม่ผ่านบ้าน (D) และต้นไม้ (T)
if(!ok(yy, xx) || c[yy][xx] == 'D' || c[yy][xx] == 'T' || d_b[yy][xx] != INF) continue;
d_b[yy][xx] = d_b[y][x] + m; // ใช้ m เพื่อเทียบกับจำนวนก้าว (steps)
q_b.push({yy, xx});
}
}
int l = 0, r = n * n, ans = -1;
while(l <= r){
int mid = l + (r - l) / 2;
if(check(mid)){
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans;
}
