/*
* Author: Nonoze
* Created: Wednesday 07/08/2024
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef _IN_LOCAL
#define dbg(...)
#endif
#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)
template<typename T> void read(T& x, bool write=0, bool write2=1, bool nothing=1) { if (write && write2) cout << x << endl; else if (write) cout << x << ' '; else cin >> x;}
template<typename T1, typename T2> void read(pair<T1, T2>& p, bool write=0, bool nothing=1, bool write2=1) { read(p.first, write, 0), read(p.second, write, 0); if (write && write2) cout << endl;}
template<typename T> void read(vector<T>& v, bool write=0) { for (auto& x : v) read(x, write, 0, 1); if (write) cout << endl; }
template<typename T1, typename T2> void read(T1& x, T2& y, bool write=0) { read(x, write), read(y, write); if (write) cout << endl; }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z, bool write=0) { read(x, write), read(y, write), read(z, write); if (write) cout << endl; }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz, bool write=0) { read(x, write), read(y, write), read(z, write), read(zz, write); if (write) cout << endl; }
template<typename T> void print(T x) { read(x, 1); }
template<typename T1, typename T2> void print(T1 x, T2 y) { read(x, y, 1); }
template<typename T1, typename T2, typename T3> void print(T1 x, T2 y, T3 z) { read(x, y, z, 1); }
template<typename T1, typename T2, typename T3, typename T4> void print(T1 x, T2 y, T3 z, T4 zz) { read(x, y, z, zz, 1); }
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define int long long
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;
void solve();
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;
// cin >> tt;
while(tt--) solve();
return 0;
}
int n, k, s, t;
vector<int> h;
vector<vector<int>> adj;
bool ok(int wait) {
vector<bool> bees(n, 0), visited(n, 0); visited[s]=1;
for (auto u: h) bees[u]=1;
queue<pair<int, pair<int, int>>> qbees;
queue<pair<int, pair<int, int>>> q2; q2.push({s, {0, 0}});
for (auto u: h) qbees.push({u, {0, 0}});
while (!q2.empty()) {
bool bee=1;
if (qbees.empty() || qbees.front().se.se>=q2.front().se.se) bee=0, swap(qbees, q2);
int u=qbees.front().fi, nb=qbees.front().se.fi, time=qbees.front().se.se; qbees.pop();
if (!bee) swap(qbees, q2);
if (!bee && time<wait) {
if (!bees[u]) q2.push({u, {0, time+1}});
continue;
}
if (bees[u] && !bee) continue;
for (auto v: adj[u]) {
if (bees[v] || (!bee && visited[v])) continue;
if (bee && t==v) continue;
if (bee) bees[v]=1;
else visited[v]=1;
if (!bee && v==t) return 1;
if (!bee) {
if (nb+1>=k) q2.push({v, {0, time+1}});
else q2.push({v, {nb+1, time}});
} else qbees.push({v, {0, time+1}});
}
}
return 0;
}
void solve() {
read(n, k);
vector<string> a(n); read(a);
adj.clear(), adj.resize(n*n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j]=='T') continue;
int act=i*n+j;
if (i && a[i-1][j]!='T') {
int nxt=(i-1)*n+j;
adj[act].pb(nxt), adj[nxt].pb(act);
}
if (j && a[i][j-1]!='T') {
int nxt=i*n+j-1;
adj[act].pb(nxt), adj[nxt].pb(act);
}
if (a[i][j]=='M') s=act;
if (a[i][j]=='D') t=act;
if (a[i][j]=='H') h.pb(act);
}
}
n*=n;
int ans=-1, l=0, r=n;
while (l<=r) {
int mid=(l+r)/2;
if (ok(mid)) ans=mid, l=mid+1;
else r=mid-1;
}
cout << ans << endl;
}
