#include <iostream>
#include <cassert>
#include <cstring>
#include <queue>
#define ll long long
using namespace std;
const int NMAX = 800;
const int di[] = { 0, 0, 1, -1 };
const int dj[] = { 1, -1, 0, 0 };
struct Triplet {
int i, j, k;
};
int n, s, istart, jstart, ifinal, jfinal;
char a[NMAX + 1][NMAX + 1];
int dh[NMAX + 1][NMAX + 1], d[NMAX + 1][NMAX + 1];
queue<pair<int, int>> qh;
bool InMat(int i, int j) {
return i >= 1 && i <= n && j >= 1 && j <= n;
}
void BFS_hives(queue<pair<int, int>>& q) {
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for(int d = 0; d < 4; d++) {
int inou = i + di[d];
int jnou = j + dj[d];
if (InMat(inou, jnou) && (a[inou][jnou] == 'G' || a[inou][jnou] == 'M') && dh[inou][jnou] == -1) {
dh[inou][jnou] = dh[i][j] + 1;
q.push({ inou, jnou });
}
}
}
}
void BFS(int istart, int jstart, int t) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = -1;
}
}
if (dh[istart][jstart] != -1 && dh[istart][jstart] <= t) {
return;
}
queue<Triplet> q;
d[istart][jstart] = t;
q.push({ istart, jstart, s });
while (!q.empty()) {
auto [i, j, k] = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++) {
int inou = i + di[dir];
int jnou = j + dj[dir];
if (InMat(inou, jnou) && a[inou][jnou] != 'T' && d[inou][jnou] == -1) {
int nxt_d = d[i][j] + (k == s ? 1 : 0);
if (dh[inou][jnou] == -1 || nxt_d <= dh[inou][jnou] - (k + 1 == s && a[inou][jnou] != 'D')) {
d[inou][jnou] = nxt_d;
q.push({ inou, jnou, (k == s ? 1 : k + 1)});
}
}
}
}
}
void Print(int d[NMAX + 1][NMAX + 1]) {
for (int i = 1; i <= n; i++, cout << '\n') {
for (int j = 1; j <= n; j++) {
cout << d[i][j] << ' ';
}
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> s;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dh[i][j] = -1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == 'M') {
istart = i;
jstart = j;
}
else if (a[i][j] == 'D') {
ifinal = i;
jfinal = j;
}
else if (a[i][j] == 'H') {
dh[i][j] = 0;
qh.push({ i, j });
}
}
}
BFS_hives(qh);
int left = 0, right = 1e9, answer = -1;
while (left <= right) {
int mid = (left + right) / 2;
BFS(istart, jstart, mid);
if (d[ifinal][jfinal] != -1) {
answer = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
cout << answer << '\n';
return 0;
}
