#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int inf = 1e9;
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k; cin >> n >> k;
vector <string> a(n);
for ( auto &u: a ) cin >> u;
ar <int,2> s, e;
vector <vector<int>> bee(n, vector <int> (n, inf));
queue <ar<int,2>> q;
for ( int i = 0; i < n; i++ ){
for ( int j = 0; j < n; j++ ){
if ( a[i][j] == 'M' ){
s = {i, j};
}
if ( a[i][j] == 'D' ){
e = {i, j};
}
if ( a[i][j] == 'H' ){
q.push({i, j});
bee[i][j] = 0;
}
}
}
auto ok = [&](int u, int v){
return u >= 0 && v >= 0 && u < n && v < n;
};
while ( !q.empty() ){
auto [u, v] = q.front();
q.pop();
for ( int i = 0; i < 4; i++ ){
int x = dx[i] + u, y = dy[i] + v;
if ( ok(x, y) && a[x][y] != 'T' && a[x][y] != 'D' ){
if ( chmin(bee[x][y], bee[u][v] + 1) ){
q.push({x, y});
}
}
}
}
auto valid = [&](int t){
if ( bee[s[0]][s[1]] <= t ){
return false;
}
vector <vector<int>> dp(n, vector <int> (n, inf));
dp[s[0]][s[1]] = t + 1;
deque <ar<int,3>> q;
q.pb({s[0], s[1], k});
while ( !q.empty() ){
auto [u, v, r] = q.front();
q.pop_front();
for ( int i = 0; i < 4; i++ ){
int x = dx[i] + u, y = dy[i] + v;
if ( !ok(x, y) || a[x][y] == 'T' ){
continue;
}
if ( r == 0 ){
if ( chmin(dp[x][y], dp[u][v] + 1) ){
q.pb({x, y, k});
}
} else if ( r == 1 ){
if ( bee[x][y] > dp[u][v] ){
if ( chmin(dp[x][y], dp[u][v]) ){
q.push_front({x, y, r - 1});
}
}
} else{
if ( bee[x][y] >= dp[u][v] ){
if ( chmin(dp[x][y], dp[u][v]) ){
q.push_front({x, y, r - 1});
}
}
}
}
}
for ( int i = 0; i < n; i++ ){
for ( int j = 0; j < n; j++ ){
}
}
return dp[e[0]][e[1]] != inf;
};
int l = 0, r = inf;
while ( l + 1 < r ){
int md = (l + r) >> 1;
if ( valid(md) ){
l = md;
} else r = md;
}
cout << (valid(l) ? l : -1);
cout << '\n';
}
