#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using pii = pair<int, int>;
using vi = vector <int>;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define ook order_of_key
#define fbo find_by_order
#define sq(x) (x) * (x)
#define N 805
int x, y, posx, posy, n, s;
int ax[4] = {0, 0, 1, -1};
int ay[4] = {1, -1, 0, 0};
string st[N];
queue <pii> que, q, bfs, mecho;
bool used[N][N], vis[N][N], pass[N][N];
bool check(int curx, int cury){
if (curx < n && cury < n && curx >= 0 && cury >= 0 && !used[curx][cury]) return true;
return false;
}
bool can(int time){;
que = q;
mecho.push(mp(x, y));
memset(pass, 0, sizeof pass);
pass[x][y] = 1;
for (int i = 0;i < n;i++)
for (int j = 0;j < n;j++)
used[i][j] = vis[i][j];
while (time--){
bfs = que;
while(!que.empty()) que.pop();
while (!bfs.empty()){
pii pos = bfs.front();
bfs.pop();
for (int i = 0;i < 4;i++)
if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T'
&& st[pos.F + ax[i]][pos.S + ay[i]] != 'D')
que.push(mp(pos.F + ax[i], pos.S + ay[i])), used[pos.F + ax[i]][pos.S + ay[i]] = 1;
}
}
while (!used[posx][posy] && !mecho.empty()){
int tmp = s;
while (tmp--){
bfs = mecho;
while (!mecho.empty()) mecho.pop();
while (!bfs.empty()){
pii pos = bfs.front();
bfs.pop();
if (pos.F == posx && pos.S == posy) return true;
if (!used[pos.F][pos.S])
for (int i = 0;i < 4;i++)
if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T'
&& !pass[pos.F + ax[i]][pos.S + ay[i]])
mecho.push(mp(pos.F + ax[i], pos.S + ay[i])), pass[pos.F + ax[i]][pos.S + ay[i]] = 1;
}
}
bfs = que;
while (!que.empty()) que.pop();
while (!bfs.empty()){
pii pos = bfs.front();
bfs.pop();
for (int i = 0;i < 4;i++)
if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T'
&& st[pos.F + ax[i]][pos.S + ay[i]] != 'D')
que.push(mp(pos.F + ax[i], pos.S + ay[i])), used[pos.F + ax[i]][pos.S + ay[i]] = 1;
}
}
return false;
}
int main (){
cin >> n>> s;
for (int i = 0;i < n;i++)
cin >> st[i];
for (int i = 0;i < n;i++)
for (int j = 0;j < n;j++){
if (st[i][j] == 'M') x = i, y = j;
if (st[i][j] == 'D') posx = i, posy = j;
if (st[i][j] == 'H') q.push(mp(i, j)), vis[i][j] = 1;
}
int l = 0, r = n * n;
while (l != r){
int mid = (l + r + 1) / 2;
if (can(mid)) l = mid;
else r = mid - 1;
}
// for (int i = 0;;i++)
// if (!can(i)){
// cout << i - 1;
// return 0;
// }
if (can(l)) cout << l<< endl;
else cout << -1 << endl;
}
