//#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define cin(v) \
for (auto &el : v) { cin >> el; }
#define cout(v) \
for (auto &el : v) { cout << el << " "; } \
cout << "\n";
using namespace std;
using ll = long long;
using db = double;
using ldb = long double;
const ldb EPS = 1e-9;
const ll LINF = 2e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 1072005019;
const ll MOD3 = 998244353;
const ldb PI = acos(-1.0);
#define int long long
vector<string> mas;
bool good(int x, int y) {
if (x >= 0 && x < mas.size() && y >= 0 && y < mas.size() && (mas[x][y] == 'G' || mas[x][y] == 'D')) {
return true;
}
return false;
}
void solve() {
int n, d;
cin >> n >> d;
mas.resize(n);
cin(mas);
vector<vector<int>> dist(n, vector<int>(n, 2e9));
queue<pair<int, int>> q;
int X = 0, Y = 0;
int X_home = 0, Y_home = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mas[i][j] == 'H') {
q.push({i, j});
dist[i][j] = 0;
}
if (mas[i][j] == 'M') {
X = i;
Y = j;
}
if (mas[i][j] == 'D') {
X_home = i;
Y_home = j;
}
}
}
while (q.size()) {
pair<int, int> p = q.front();
q.pop();
int x = p.first, y = p.second;
if (x >= 1 && (mas[x - 1][y] == 'G' || mas[x - 1][y] == 'M')) {
if (dist[x - 1][y] > dist[x][y] + 1) {
dist[x - 1][y] = dist[x][y] + 1;
q.push({x - 1, y});
}
}
if (x + 1 < n && (mas[x + 1][y] == 'G'|| mas[x + 1][y] == 'M')) {
if (dist[x + 1][y] > dist[x][y] + 1) {
dist[x + 1][y] = dist[x][y] + 1;
q.push({x + 1, y});
}
}
if (y >= 1 && (mas[x][y - 1] == 'G'|| mas[x][y - 1] == 'M')) {
if (dist[x][y - 1] > dist[x][y] + 1) {
dist[x][y - 1] = dist[x][y] + 1;
q.push({x, y - 1});
}
}
if (y + 1 < n && (mas[x][y + 1] == 'G' || mas[x][y + 1] == 'M')) {
if (dist[x][y + 1] > dist[x][y] + 1) {
dist[x][y + 1] = dist[x][y] + 1;
q.push({x, y + 1});
}
}
}
int l = -1, r = 2e9;
while (r - l > 1) {
int mid = l + (r - l) / 2;
queue<pair<int, int>> q;
vector<vector<int>> dist2(n, vector<int>(n, 2e9));
q.push({X, Y});
dist2[X][Y] = mid * d;
if (dist[X][Y] * d <= dist2[X][Y]) {
r = mid;
continue;
}
while (q.size()) {
pair<int, int> p = q.front();
q.pop();
int x = p.first, y = p.second;
if (good(x - 1, y)) {
if (dist2[x - 1][y] > dist2[x][y] + 1 && (mas[x - 1][y] == 'D' || dist[x - 1][y] * d > dist2[x][y] + 1)) {
dist2[x - 1][y] = dist2[x][y] + 1;
q.push({x - 1, y});
}
}
if (good(x + 1, y)) {
if (dist2[x + 1][y] > dist2[x][y] + 1 && (mas[x + 1][y] == 'D' || dist[x + 1][y] * d > dist2[x][y] + 1)) {
dist2[x + 1][y] = dist2[x][y] + 1;
q.push({x + 1, y});
}
}
if (good(x, y - 1)) {
if (dist2[x][y - 1] > dist2[x][y] + 1 && (mas[x][y - 1] == 'D' || dist[x][y - 1] * d > dist2[x][y] + 1)) {
dist2[x][y - 1] = dist2[x][y] + 1;
q.push({x, y - 1});
}
}
if (good(x, y + 1)) {
if (dist2[x][y + 1] > dist2[x][y] + 1 && (mas[x][y + 1] == 'D' || dist[x][y + 1] * d > dist2[x][y] + 1)) {
dist2[x][y + 1] = dist2[x][y] + 1;
q.push({x, y + 1});
}
}
}
if (dist2[X_home][Y_home] != 2e9) {
l = mid;
} else {
r = mid;
}
}
cout << l;
return;
}
signed main() {
ll interactive = 0;
ll multitest = 0;
if (!interactive) {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
if (multitest) {
ll T;
cin >> T;
while (T--) {
solve();
}
} else {
solve();
}
return 0;
}
