#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define all(a) a.begin(), a.end()
#define el '\n'
const int maxN = 805;
const int base = 311;
const int MOD = 1e9+7;
const int INF = 1e18;
const int NEG_INF = -1e18;
const int MAX_DAYS = 1000;
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
int n, m, k, q, x;
// string S, T;
int S;
int dist_mecho[maxN][maxN];
int dist_bee[maxN][maxN];
int par[maxN], deg[maxN];
bool visited[maxN];
vector<int> g[maxN];
string grid[maxN];
string dir_char = "LRUD";
pii st, ed;
vector<pii> bees;
bool inside(int x, int y) {
return (x > 0 && x <= n && y > 0 && y <= m && grid[x][y] != 'T');
}
// void bfs(pii st) {
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++){
// dist[i][j] = INF;
// par[i][j] = -1;
// }
// }
// queue<tuple<int,int>> q;
// q.push({st.fi, st.se});
// dist[st.fi][st.se] = 0;
// while (!q.empty()) {
// auto [x, y] = q.front();
// q.pop();
// if (x == ed.fi && y == ed.se) return;
// for(int k = 0; k < 4; k++){
// int nx = x + dx[k], ny = y + dy[k];
// if(!inside(nx,ny)) continue;
// if(dist[nx][ny] > dist[x][y] + 1){
// dist[nx][ny] = dist[x][y] + 1;
// par[nx][ny] = k;
// q.push({nx,ny});
// }
// }
// }
// }
bool bfs_mecho(int time_eat) {
if (time_eat * 1 >= dist_bee[st.fi][st.se]) return false;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist_mecho[i][j] = INF;
}
}
queue<pii> q;
q.push({st.fi, st.se});
dist_mecho[st.fi][st.se] = 0;
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
if (x == ed.fi && y == ed.se) return true;
int steps = dist_mecho[x][y] + 1;
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
// int cur_time = time_eat + (steps - 1) / S + 1;
int cur_time = time_eat + steps/S;
if(!inside(nx,ny) || cur_time >= dist_bee[nx][ny]) continue;
if(dist_mecho[nx][ny] > dist_mecho[x][y] + 1){
dist_mecho[nx][ny] = dist_mecho[x][y] + 1;
q.push({nx,ny});
}
}
}
return false;
}
void bfs_bee(){
queue<pii> q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist_bee[i][j] = INF;
}
}
for(auto bee : bees){
dist_bee[bee.fi][bee.se] = 0;
q.push({bee.fi, bee.se});
}
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(!inside(nx,ny) || grid[nx][ny] == 'D') continue;
if(dist_bee[nx][ny] > dist_bee[x][y] + 1){
dist_bee[nx][ny] = dist_bee[x][y] + 1;
q.push({nx,ny});
}
}
}
}
// void Trace() {
// if (dist[ed.fi][ed.se] == INF) {
// cout << "NO" << el;
// return;
// }
// cout << "YES" << el;
// cout << dist[ed.fi][ed.se] << el;
// string path = "";
// int cur_x = ed.fi;
// int cur_y = ed.se;
// while (cur_x != st.fi || cur_y != st.se) {
// int k = par[cur_x][cur_y];
// path += dir_char[k];
// cur_x -= dx[k];
// cur_y -= dy[k];
// }
// reverse(path.begin(), path.end());
// cout << path << el;
// }
void run_test() {
cin >> n >> S;
m = n;
for(int i = 1; i <= n; i++){
string s;
cin >> s;
s = '_' + s;
grid[i] = s;
for(int j = 1; j <= m; j++){
if(grid[i][j] == 'M') st = {i, j};
if(grid[i][j] == 'D') ed = {i, j};
if(grid[i][j] == 'H'){
bees.push_back({i,j});
}
}
}
bfs_bee();
int lo = 0; int hi = INF;
while(lo <= hi){
int mid = (lo + hi) >> 1;
if(bfs_mecho(mid)) lo = mid + 1;
else hi = mid - 1;
}
cout << hi;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("atlarge.in", "r", stdin);
// freopen("atlarge.out", "w", stdout);
int test = 1;
// cin >> test;
while (test-- > 0)
{
run_test();
}
}
