#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, s;
int x3, x2, y3, y2;
vector<vector<char>> grid;
vector<vector<int>> tim; //saves time the bees get there
vector<vector<int>> dist; //saves latest time can leave current spot to get to house on time
vector<pair<int, int>> direc = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};
bool check(int i, int j) {
if (i < 0 || j < 0 || i >= n || j >= n) return false; //out of bounds
if (grid[i][j] == 'M' || grid[i][j] == 'G') return true; //good next field
return false;
}
void bfs1() {
queue<tuple<int, int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'H') q.push({0, i, j});
}
}
while (!q.empty()) {
auto [d, i, j] = q.front();
q.pop();
if (tim[i][j] <= d) continue;
tim[i][j] = d;
for (auto [x, y] : direc) {
if (check(i+x, j+y)) q.push({d+1, i+x, j+y});
}
}
}
void bfs2() {
priority_queue<tuple<int, int, int, int>> pq; //dist, steps, i, j
pq.push({1e9, s, x2, y2});
while (!pq.empty()) {
auto [d, step, i, j] = pq.top();
//~ cout << d << " " << i << " " << j << " " << step << endl;
pq.pop();
if (tim[i][j] <= d) {
d = tim[i][j]-1;
step = s;
}
if (step == 0) {
d--;
step = s;
}
if (dist[i][j] >= d) continue;
dist[i][j] = d;
for (auto [x, y] : direc) {
if (check(i+x, j+y)) pq.push({d, step-1, i+x, j+y});
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> s;
grid = vector<vector<char>> (n, vector<char> (n));
tim = vector<vector<int>> (n, vector<int> (n, 1e9));
dist = vector<vector<int>> (n, vector<int> (n, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
if (grid[i][j] == 'D') {
x2 = i; y2 = j;
}
if (grid[i][j] == 'M') {
x3 = i; y3 = j;
}
}
}
bfs1(); //calculates how long it takes for fields to be infected with bees
//now need to calc movement somehow
bfs2(); //seg fault occurs in here
cout << dist[x3][y3] << endl;
}
