#include <bits/stdc++.h>
// #include <iostream>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x << " " <<endl;
#define printp(a) for(auto x : a) cout << x.first << " " << x.second <<endl;
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
ll t, n, m, s, k, a, b, tot;
char mat[1000][1000];
bool visited[1000][1000];
void solve() {
cin >> n >> s;
f(i, 0, n) f(j, 0, n) cin >> mat[i][j];
vector<vpl> bees;
queue<pll> q;
f(i, 0, n) {
f(j, 0, n) {
if (mat[i][j] == 'H') {
visited[i][j] = 1;
q.push({i, j});
}
}
}
vpl vec;
ll cnt = q.size();
while (!q.empty()) {
pll curr = q.front();
vec.pb(curr);
q.pop();
ll x = curr.F, y = curr.S;
if (x > 0 && !visited[x-1][y]) {
if (mat[x-1][y] == 'G' || mat[x-1][y] == 'M') q.push({x-1, y});
visited[x-1][y] = 1;
}
if (x < n-1 && !visited[x+1][y]) {
if (mat[x+1][y] == 'G' || mat[x+1][y] == 'M') q.push({x+1, y});
visited[x+1][y] = 1;
}
if (y > 0 && !visited[x][y-1]) {
if (mat[x][y-1] == 'G' || mat[x][y-1] == 'M') q.push({x, y-1});
visited[x][y-1] = 1;
}
if (y < n-1 && !visited[x][y+1]) {
if (mat[x][y+1] == 'G' || mat[x][y+1] == 'M') q.push({x, y+1});
visited[x][y+1] = 1;
}
cnt--;
if (cnt == 0) {
bees.pb(vec);
vec.clear();
cnt = q.size();
}
}
pll start;
f(i, 0, n) f(j, 0, n) if (mat[i][j] == 'M') {start = {i, j}; break;}
ll l = 0, r = bees.size() - 1;
tot = -1;
while (l <= r) {
ll m = (l + r) / 2;
vector<vb> visited(n, vb(n, 0));
vector<vb> infect(n, vb(n, 0));
cf(i, 0, m) for (pll bee : bees[i]) infect[bee.F][bee.S] = 1;
queue<pll> q;
q.push(start);
visited[start.F][start.S] = 1;
bool reach = false;
ll mv = 0, cnt = 1;
while (!q.empty()) {
pll curr = q.front();
q.pop();
ll x = curr.F, y = curr.S;
if (!infect[x][y]) {
if (x > 0 && !visited[x-1][y]) {
if (mat[x-1][y] == 'D') {
reach = true;
break;
} else if (mat[x-1][y] == 'G') q.push({x-1, y});
visited[x-1][y] = 1;
}
if (x < n-1 && !visited[x+1][y]) {
if (mat[x+1][y] == 'D') {
reach = true;
break;
} else if (mat[x+1][y] == 'G') q.push({x+1, y});
visited[x+1][y] = 1;
}
if (y > 0 && !visited[x][y-1]) {
if (mat[x][y-1] == 'D') {
reach = true;
break;
} else if (mat[x][y-1] == 'G') q.push({x, y-1});
visited[x][y-1] = 1;
}
if (y < n-1 && !visited[x][y+1]) {
if (mat[x][y+1] == 'D') {
reach = true;
break;
} else if (mat[x][y+1] == 'G') q.push({x, y+1});
visited[x][y+1] = 1;
}
}
cnt--;
if (cnt == 0) {
mv++;
cnt = q.size();
if (mv % s == 0) {
for (pll bee : bees[m + mv/s]) infect[bee.F][bee.S] = 1;
}
}
}
if (reach) {
l = m + 1;
tot = m;
} else r = m - 1;
} cout << tot <<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
t = 1;
while (t--) {
solve();
}
}
