#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define v(x) v[x.first][x.second]
#define bs(x) bs[x.first][x.second]
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
int n, s;
vector<vector<bool>> mp;
vector<pii> hives;
pii strt;
pii trgt;
vector<pii> adj = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool in(pii x){
if(x.first < 0 || x.first >= n) return 0;
if(x.second < 0 || x.second >= n) return 0;
return 1;
}
bool can(int t){
vector<vector<bool>> v = mp;
vector<vector<bool>> bs;
bs.resize(n, vector<bool>(n));
queue<pair<pii, int>> q, bq;
q.push({strt, t});
for(auto i : hives) bq.push({i, 0});
while(bq.size() && bq.front().second < t){
auto [a, d] = bq.front(); bq.pop();
for (auto &&o : adj) {
pii b = {a.first + o.first, a.second + o.second};
if(in(b) && !v(b) && !bs(b)){
bs(b) = true;
bq.push({b, d + 1});
}
}
}
int nt = t;
while(q.size()){
nt += s;
t++;
while(q.size() && q.front().second < nt){
auto [a, d] = q.front(); q.pop();
if(bs(a)) continue;
for (auto &&o : adj) {
pii b = {a.first + o.first, a.second + o.second};
if(in(b) && !v(b) && !bs(b)){
v(b) = true;
q.push({b, d + 1});
}
if(b == trgt) return true;
}
}
while(bq.size() && bq.front().second < t){
auto [a, d] = bq.front(); bq.pop();
for (auto &&o : adj) {
pii b = {a.first + o.first, a.second + o.second};
if(in(b) && !v(b) && !bs(b)){
bs(b) = true;
bq.push({b, d + 1});
}
}
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
mp.resize(n, vector<bool>(n));
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0; j < n; j++) {
char a = s[j];
if(a == 'M') strt = {i, j};
else if(a == 'D') { trgt = {i, j}; mp[i][j] = 1;}
else if(a == 'H') hives.push_back({i, j});
else if(a == 'T') mp[i][j] = 1;
}
}
int l = 0, r = n * n, mid;
while(l < r){
mid = (l + r + 1) / 2;
if(can(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
