#include <bits/stdc++.h>
using namespace std;
const int INF = 2000000005;
char grid[800][800];
int bee_dist[800][800];
vector<pair<int,int>> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
bool valid(int y, int x, int n) {
return y >= 0 && y < n && x >= 0 && x < n && grid[y][x] != 'T';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, s;
cin >> n >> s;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> grid[i][j];
}
}
pair<int,int> bear_start, dest;
vector<pair<int,int>> hives;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if(grid[i][j]=='M') bear_start = {i,j};
if(grid[i][j]=='D') dest = {i,j};
if(grid[i][j]=='H') hives.push_back({i,j});
}
}
// Compute bees' arrival times (in minutes) using a simple BFS.
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
bee_dist[i][j] = INF;
}
}
queue<pair<int,int>> qb;
for(auto &h : hives){
int y = h.first, x = h.second;
bee_dist[y][x] = 0;
qb.push({y,x});
}
while(!qb.empty()){
auto [y, x] = qb.front();
qb.pop();
for(auto d : dirs){
int ny = y + d.first, nx = x + d.second;
if(!valid(ny,nx,n)) continue;
// Bees do not enter Mecho's home.
if(grid[ny][nx]=='D') continue;
if(bee_dist[ny][nx] > bee_dist[y][x] + 1){
bee_dist[ny][nx] = bee_dist[y][x] + 1;
qb.push({ny,nx});
}
}
}
// Compute minimal minutes required for Mecho to reach home from every cell.
// In one minute, Mecho can make up to s steps. We perform a multi-minute BFS
// from Mecho's home (destination) over the grid.
vector<vector<int>> escape(n, vector<int>(n, INF));
queue<pair<int,int>> mq;
escape[dest.first][dest.second] = 0;
mq.push(dest);
while(!mq.empty()){
auto [cy, cx] = mq.front();
mq.pop();
int nextTime = escape[cy][cx] + 1;
vector<vector<bool>> used(n, vector<bool>(n, false));
queue<tuple<int,int,int>> subq; // (y, x, steps taken in current minute)
subq.push({cy, cx, 0});
used[cy][cx] = true;
while(!subq.empty()){
auto [y, x, steps] = subq.front();
subq.pop();
if(steps == s) continue;
for(auto d : dirs){
int ny = y + d.first, nx = x + d.second;
if(!valid(ny, nx, n)) continue;
if(!used[ny][nx]){
used[ny][nx] = true;
if(escape[ny][nx] > nextTime){
escape[ny][nx] = nextTime;
mq.push({ny,nx});
}
subq.push({ny, nx, steps + 1});
}
}
}
}
// The "possible" function: can Mecho, by waiting w minutes before leaving,
// follow a safe path from his start to home? At any cell (except home) he must
// arrive strictly before the bees.
auto possible = [&](int w) -> bool {
// At the start cell, if waiting plus minimal required time from here is not less
// than the bees' arrival time, then it's impossible.
if(w + escape[bear_start.first][bear_start.second] >= bee_dist[bear_start.first][bear_start.second])
return false;
vector<vector<bool>> vis(n, vector<bool>(n, false));
queue<pair<int,int>> qu;
qu.push(bear_start);
vis[bear_start.first][bear_start.second] = true;
while(!qu.empty()){
auto [y, x] = qu.front();
qu.pop();
if(grid[y][x]=='D')
return true;
for(auto d : dirs){
int ny = y + d.first, nx = x + d.second;
if(!valid(ny, nx, n)) continue;
if(vis[ny][nx]) continue;
// For cell (ny, nx), if the total time (waiting w plus the minimal minutes
// needed from there) is strictly less than the time bees arrive, then we
// consider it safe.
if(w + escape[ny][nx] < bee_dist[ny][nx]){
vis[ny][nx] = true;
qu.push({ny,nx});
}
}
}
return false;
};
int lo = 0, hi = 1000000, ans = -1;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
if(possible(mid)){
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << ans << "\n";
return 0;
}
