#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int INF = 1e9;
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, S;
if(!(cin >> N >> S)) return 0;
vector<string> a(N);
for(int i=0;i<N;i++) cin >> a[i];
vector<vector<int>> beeDist(N, vector<int>(N, INF));
queue<pii> q;
pii start = {-1,-1}, home = {-1,-1};
for(int r=0;r<N;r++){
for(int c=0;c<N;c++){
if(a[r][c]=='H'){
beeDist[r][c] = 0;
q.push({r,c});
} else if(a[r][c]=='M') start = {r,c};
else if(a[r][c]=='D') home = {r,c};
}
}
// BFS for bees: they can move into any cell that is NOT 'T' and NOT 'D'
while(!q.empty()){
auto [r,c] = q.front(); q.pop();
int d = beeDist[r][c];
for(int k=0;k<4;k++){
int nr=r+dr[k], nc=c+dc[k];
if(nr<0||nr>=N||nc<0||nc>=N) continue;
if(a[nr][nc]=='T' || a[nr][nc]=='D') continue; // bees can't go through trees or into D
if(beeDist[nr][nc] > d+1){
beeDist[nr][nc] = d+1;
q.push({nr,nc});
}
}
}
// make D effectively safe: set beeDist[D] = INF (already INF because we didn't allow bees into D),
// but ensure it explicitly:
beeDist[home.first][home.second] = INF;
// Helper: check if wait = w is possible
auto can = [&](int w)->bool{
// must be safe at start cell at time w
if(beeDist[start.first][start.second] <= w) return false;
// visited_global: cells we've already used as start-of-minute in previous iterations (avoid re-visiting forever)
vector<vector<char>> used(N, vector<char>(N, 0));
queue<pii> frontier; // cells that are start-of-minute at current time t
used[start.first][start.second] = 1;
frontier.push(start);
int t = w; // current minute index (we start moving at minute t = w)
// If start is itself D (unlikely by problem statement), success
if(start == home) return true;
while(!frontier.empty()){
// BFS limited to depth S from all frontier sources, allowed to step only through cells with beeDist > t
vector<pii> nextFront; // will be start-of-minute for t+1 (only cells with beeDist > t+1)
queue<pair<pii,int>> qq;
vector<vector<char>> seen(N, vector<char>(N,0)); // seen within this minute's multi-source S-BFS
// push all frontier sources as depth 0
int fsz = frontier.size();
while(fsz--){
auto p = frontier.front(); frontier.pop();
qq.push({p,0});
seen[p.first][p.second] = 1;
}
while(!qq.empty()){
auto cur = qq.front(); qq.pop();
int r = cur.first.first, c = cur.first.second, depth = cur.second;
// If we reach home at any time, success
if(r==home.first && c==home.second) return true;
if(depth == S) continue; // can't go deeper this minute
for(int k=0;k<4;k++){
int nr=r+dr[k], nc=c+dc[k];
if(nr<0||nr>=N||nc<0||nc>=N) continue;
if(seen[nr][nc]) continue;
// Mecho cannot go on trees or on H (hive). He can go on G, M, D.
if(a[nr][nc]=='T' || a[nr][nc]=='H') continue;
// He cannot step into a cell that has already been occupied by bees at start of minute t:
if(beeDist[nr][nc] <= t) continue;
seen[nr][nc] = 1;
qq.push({{nr,nc}, depth+1});
}
}
// from seen (cells reached within <=S steps this minute), construct nextFront of cells that survive to next minute
for(int r=0;r<N;r++){
for(int c=0;c<N;c++){
if(!seen[r][c]) continue;
// If any reached cell is home we would have returned earlier.
if(r==home.first && c==home.second) return true;
// to survive to next minute (i.e., at start of minute t+1) Mecho's cell must have beeDist > t+1
if(beeDist[r][c] > t+1){
if(!used[r][c]){
used[r][c] = 1;
nextFront.push_back({r,c});
}
}
}
}
// push nextFront into frontier queue
for(auto &p: nextFront) frontier.push(p);
// increment minute
t++;
}
return false;
};
// Binary search maximum w
int lo = 0, hi = N*N + 5; // hi is exclusive upper bound; safe big
int ans = -1;
while(lo <= hi){
int mid = lo + (hi-lo)/2;
if(can(mid)){
ans = mid;
lo = mid+1;
} else hi = mid-1;
}
if(ans < 0) cout << -1 << "\n";
else cout << ans << "\n";
return 0;
}
