#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF = 1e6;
vector<vector<int>> time_bees;
void bfs_bees(vector<pair<int, int>>& hives, int n, vector<vector<char>>& map) {
queue<pair<int, int>> q;
for (pair<int, int> h : hives) {
q.push(h);
time_bees[h.first][h.second] = 0;
}
while (!q.empty()) {
pair<int, int> pos = q.front();
q.pop();
int i = pos.first, j = pos.second;
if (i > 0 && time_bees[i-1][j] == INF && map[i-1][j] == 'G') {
time_bees[i-1][j] = time_bees[i][j]+1;
q.push({i-1, j});
}
if (i < n-1 && time_bees[i+1][j] == INF && map[i+1][j] == 'G') {
time_bees[i+1][j] = time_bees[i][j]+1;
q.push({i+1, j});
}
if (j > 0 && time_bees[i][j-1] == INF && map[i][j-1] == 'G') {
time_bees[i][j-1] = time_bees[i][j]+1;
q.push({i, j-1});
}
if (j < n-1 && time_bees[i][j+1] == INF && map[i][j+1] == 'G') {
time_bees[i][j+1] = time_bees[i][j]+1;
q.push({i, j+1});
}
}
}
bool CanGetHome(pair<int, int> r, vector<vector<char>>& map, int s, int t, pair<int, int> d) {
int n = (int)map.size();
queue<pair<pair<int, int>, int>> q;
vector<vector<int>> visited(n, vector<int>(n, 0));
visited[r.first][r.second] = 1;
q.push({r, s*t});
while (!q.empty()) {
pair<int, int> pos = q.front().first;
int steps = q.front().second;
q.pop();
int i = pos.first, j = pos.second;
if (pos == d) return true;
if (pos != r) {
if (steps%s == 0) {
if ((steps+s-1)/s >= time_bees[i][j]) continue;
} else if ((steps+s-1)/s > time_bees[i][j]) continue;
}
if (i > 0 && !visited[i-1][j] && map[i-1][j] == 'G') {
visited[i-1][j] = 1;
q.push({{i-1, j}, steps+1});
}
if (i < n-1 && !visited[i+1][j] && map[i+1][j] == 'G') {
visited[i+1][j] = 1;
q.push({{i+1, j}, steps+1});
}
if (j > 0 && !visited[i][j-1] && map[i][j-1] == 'G') {
visited[i][j-1] = 1;
q.push({{i, j-1}, steps+1});
}
if (j < n-1 && !visited[i][j+1] && map[i][j+1] == 'G') {
visited[i][j+1] = 1;
q.push({{i, j+1}, steps+1});
}
}
return false;
}
int main() {
int n, s;
cin >> n >> s;
vector<vector<char>> map(n, vector<char>(n));
vector<pair<int, int>> hives;
pair<int, int> mecho, home;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> map[i][j];
if (map[i][j] == 'H') hives.pb({i, j});
else if (map[i][j] == 'M') {
mecho = {i, j};
map[i][j] = 'G';
} else if (map[i][j] == 'D') home = {i, j};
}
}
time_bees = vector<vector<int>>(n, vector<int>(n, INF));
map[home.first][home.second] = 'G';
bfs_bees(hives, n, map);
int l = 0, r = time_bees[home.first][home.second]+1, ans = -1;
while (l <= r) {
int m = (l+r)/2;
if (CanGetHome(mecho, map, s, m, home)) {
l = m+1;
ans = m;
} else r = m-1;
}
cout << ans << '\n';
return 0;
}
