#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 801;
char a [maxn][maxn];
char c [maxn][maxn];
bool vis [maxn][maxn];
bool bad [maxn][maxn];
int n,s, sx, sy, ex, ey;
queue <pair <int, int> > startq;
int dx[] = {-1, 0, 1, -1};
int dy[] = {0, 1, 0, -1};
bool check (int minutes) {
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
vis[i][j] = 0;
bad[i][j] = 0;
c[i][j] = a[i][j];
}
}
queue <pair <int, int> > bear, bee = startq;
bear.push({sx, sy});
// move bees for minutes before starting search
while (minutes--) {
int k = bee.size();
for (int i = 0; i < k; i++){
int x = bee.front().first, y = bee.front().second;
bad[x][y] = 1;
bee.pop();
for (int j = 0; j < 4; j++){
int nx = x + dx[j], ny = y + dy[j];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || bad[nx][ny] ||
c[nx][ny] == 'T' || c[nx][ny] == 'D' || c[nx][ny] == 'H') continue;
c[nx][ny] = 'H';
bad[nx][ny] = 1;
bee.push({nx, ny});
}
}
}
while (!bear.empty()){
for (int z = 0; z < s; z++){
int k = bear.size();
for (int i = 0; i < k; i++){
int x = bear.front().first, y = bear.front().second;
bear.pop();
if (bad[x][y]) continue;
for (int j = 0; j < 4; j++){
int nx = x + dx[j], ny = y + dy[j];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] ||
c[nx][ny] == 'T' || c[nx][ny] == 'H') continue;
if (c[nx][ny] == 'D') return 1;
vis[nx][ny] = 1;
bear.push({nx, ny});
}
}
}
int k = bee.size();
for (int i = 0; i < k; i++){
int x = bee.front().first, y = bee.front().second;
bad[x][y] = 1;
bee.pop();
for (int j = 0; j < 4; j++){
int nx = x + dx[j], ny = y + dy[j];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || bad[nx][ny] ||
c[nx][ny] == 'T' || c[nx][ny] == 'D' || c[nx][ny] == 'H') continue;
c[nx][ny] = 'H';
bad[nx][ny] = 1;
bee.push({nx, ny});
}
}
}
return 0;
}
int main() {
cin >> n >> s;
for (int i = 0; i < n; i++){
cin >> a[i];
for (int j = 0; j < n; j++){
if (a[i][j] == 'M') {
sx = i, sy = j;
}
if (a[i][j] == 'D') {
ex = i, ey = j;
}
if (a[i][j] == 'H') {
startq.push({i,j});
}
}
}
// check(0);
int l = 0, r = maxn * maxn, rs = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
rs = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
cout << rs;
return 0;
}
