#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 800 + 5, INF = 1e9, MAX_T = MAX_N * MAX_N;
int n, s;
char arr[MAX_N][MAX_N];
bool bee_seen[MAX_N][MAX_N];
int bee_dist[MAX_N][MAX_N]; // INF if unreachable
queue<pii> bee_order;
void bee_bfs() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (arr[i][j] == 'H') {
bee_seen[i][j] = true;
bee_order.push({i, j});
} else
bee_dist[i][j] = INF;
}
while (bee_order.size()) {
int i = bee_order.front().first, j = bee_order.front().second;
bee_order.pop();
vector<pii> delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (pii in : delta) {
int new_i = i + in.first, new_j = j + in.second;
if (new_i < 1 || new_i > n || new_j < 1 || new_j > n) continue;
if (arr[new_i][new_j] != 'G') continue;
if (bee_seen[new_i][new_j]) continue;
bee_seen[new_i][new_j] = true;
bee_dist[new_i][new_j] = bee_dist[i][j] + 1;
bee_order.push({new_i, new_j});
}
}
}
bool check_seen[MAX_N][MAX_N];
int check_dist[MAX_N][MAX_N]; // INF if unreachable
queue<pii> check_order;
bool check(int t) {
pii finish = {0, 0};
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] == 'M') {
check_seen[i][j] = true;
check_dist[i][j] = 0;
check_order.push({i, j});
} else {
check_seen[i][j] = false;
check_dist[i][j] = INF;
}
if (arr[i][j] == 'D')
finish = {i, j};
}
}
while (check_order.size()) {
int i = check_order.front().first, j = check_order.front().second;
check_order.pop();
// cout << t << ": " << i << " " << j << endl;
vector<pii> delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (pii in : delta) {
int new_i = i + in.first, new_j = j + in.second;
if (new_i < 1 || new_i > n || new_j < 1 || new_j > n) continue;
if (arr[new_i][new_j] == 'T') continue;
if (check_seen[new_i][new_j]) continue;
int new_dist = check_dist[i][j] + 1;
if (bee_dist[new_i][new_j] < t + (new_dist / s)) continue;
check_dist[new_i][new_j] = new_dist;
check_seen[new_i][new_j] = true;
check_order.push({new_i, new_j});
}
}
return check_seen[finish.first][finish.second];
}
int bin_search() {
int lo = 1, hi = MAX_T;
while (lo != hi) {
int mid = ceil((lo + hi) / (double) 2);
if (check(mid)) lo = mid;
else hi = mid - 1;
}
if (check(lo)) return lo;
else return -1;
}
int main() {
// freopen("mecho.in", "r", stdin);
cin >> n >> s;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> arr[i][j];
bee_bfs();
int ans = bin_search();
if (ans != -1) ans--;
cout << ans << '\n';
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++)
// cout << bee_dist[i][j] << " ";
// cout << endl;
// }
}
