#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 7;
const int INF = (int) 1e9 + 7;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int n;
int speed;
int r1, c1;
int r2, c2;
int a[N][N];
int dist_m[N][N];
int dist_b[N][N];
vector<pair<int, int>> ord;
void compute(int dist[N][N], vector<pair<int, int>> init) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = INF;
}
}
queue<pair<int, int>> q;
for (auto &it : init) {
dist[it.first][it.second] = 0;
q.push(it);
}
while (!q.empty()) {
auto it = q.front();
int r = it.first;
int c = it.second;
ord.push_back(it);
q.pop();
for (int k = 0; k < 4; k++) {
int rn = r + dr[k];
int cn = c + dc[k];
if (a[rn][cn] && dist[rn][cn] == INF) {
dist[rn][cn] = 1 + dist[r][c];
q.push({rn, cn});
}
}
}
}
int dist[N][N];
bool ok[N][N];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
/// freopen ("input", "r", stdin);
cin >> n >> speed;
vector<pair<int, int>> bees;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 1; j <= n; j++) {
char ch = s[j - 1];
if (ch == 'T') {
a[i][j] = 0;
continue;
}
if (ch == 'G') {
a[i][j] = 1;
continue;
}
if (ch == 'M') {
r1 = i;
c1 = j;
a[i][j] = 1;
continue;
}
if (ch == 'D') {
r2 = i;
c2 = j;
a[i][j] = 1;
continue;
}
if (ch == 'H') {
bees.push_back({i, j});
continue;
}
}
}
vector<pair<int, int>> m;
m.push_back({r1, c1});
compute(dist_b, bees);
ord.clear();
compute(dist_m, m);
int low = 0, high = dist_b[r1][c1] - 1, sol = -1;
while (low <= high) {
int stay = (low + high) / 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ok[i][j] = 0;
}
}
ok[r1][c1] = 1;
bool f = 0;
for (auto &it : ord) {
if (ok[it.first][it.second]) {
if (it.first == r2 && it.second == c2) f = 1;
int r = it.first, c = it.second;
for (int k = 0; k < 4; k++) {
int rn = r + dr[k];
int cn = c + dc[k];
int the_dist = dist_m[rn][cn];
if (the_dist % speed != 0) {
ok[rn][cn] |= 1;
} else {
ok[rn][cn] |= ((stay + the_dist / speed) < dist_b[rn][cn]);
}
}
}
}
/* for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (ok[i][j]) {
cout << (stay + (dist_m[i][j] + speed - 1) / speed) << " ";
} else {
cout << "- ";
}
///cout << ok[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (ok[i][j]) {
cout << dist_b[i][j] << " ";
} else {
cout << "- ";
}
///cout << ok[i][j] << " ";
}
cout << "\n";
}
exit(0);*/
if (f) {
sol = stay;
low = stay + 1;
} else {
high = stay - 1;
}
}
cout << sol << "\n";
return 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int val = dist_m[i][j];
if (val == INF) {
cout << "- ";
} else {
cout << val << " ";
}
}
cout << "\n";
}
return 0;
}
