#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e3+10;
char matrix[mxN][mxN];
bool vis[mxN][mxN];
int d[mxN][mxN];
int n, s;
pair<int, int> start, finish;
vector<int> xy = {1, 0, -1, 0}, yx = {0, 1, 0, -1};
bool valid(int x, int y, vector<vector<char>> &curr) {
return (x >= 0 && x < n && y < n && y >= 0 && !vis[x][y] &&
curr[x][y] == 'G');
}
bool valid1(int x, int y, vector<vector<char>> &curr) {
return (x >= 0 && x < n && y < n && y >= 0 &&
(curr[x][y] == 'G' || curr[x][y] == 'D'));
}
bool just[mxN][mxN];
void dfs(vector<vector<char>> &curr, int i, int j) {
vis[i][j] = true;
for(int k = 0; k < 4; k++) {
int a = i+xy[k], b = j+yx[k];
if(valid(a, b, curr)) {
curr[a][b] = 'H';
if(a > i) just[a][b] = true;
if(a == i && b > j) just[a][b] = true;
}
}
}
void exec(vector<vector<char>> &curr) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(curr[i][j] == 'H' && !vis[i][j] && !just[i][j]) {
dfs(curr, i, j);
}
just[i][j] = false;
}
}
}
bool f(int mid) {
memset(vis, false, sizeof vis);
memset(d, 0x3F, sizeof d);
vector<vector<char>> curr(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
curr[i].push_back(matrix[i][j]);
}
}
for(int k = 0; k < mid; k++) {
exec(curr);
}
queue<array<int, 3>> q;
q.push({start.first, start.second, 0});
d[start.first][start.second] = 0;
int last = 0;
while(!q.empty()) {
auto x = q.front()[0], y = q.front()[1], dist = q.front()[2];
q.pop();
if((dist != last) && (last % s == 0) && last) {
exec(curr);
}
last = dist;
if(curr[x][y] == 'H') continue;
if(x == finish.first && y == finish.second) {
return true;
}
int new_d = d[x][y] + 1;;
for(int k = 0; k < 4; k++) {
int a = x + xy[k], b = y + yx[k];
if(valid1(a, b, curr) && new_d < d[a][b]) {
d[a][b] = new_d;
q.push({a, b, dist+1});
}
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cin >> matrix[i][j];
if(matrix[i][j] == 'M') {
start = {i, j};
matrix[i][j] = 'G';
}
if(matrix[i][j] == 'D') {
finish = {i, j};
}
}
}
int l = 0, r = n*n;
while(l < r) {
int mid = l + (r - l + 1) / 2;
if(f(mid)) {
l = mid;
}
else r = mid-1;
}
cout << (f(l) ? l : -1);
}
