#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, s;
cin >> n >> s;
vector<vector<char>> grid(n, vector<char>(n));
queue<pair<ll, pair<int, int>>> h;
pair<int, int> m;
pair<int, int> dest;
vector<pair<int, int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<ll>> dist(n, vector<ll>(n, 1e9));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> grid[i][j];
if (grid[i][j] == 'H'){
h.push({0, {i, j}});
dist[i][j] = 0;
}
if (grid[i][j] == 'M'){
m = {i, j};
}
if (grid[i][j] == 'D'){
dest = {i, j};
}
}
}
while (!h.empty()){
int x = h.front().second.first;
int y = h.front().second.second;
ll d = h.front().first;
h.pop();
if (dist[x][y] != d) continue;
for (auto ne : dir){
int nx = x + ne.first;
int ny = y + ne.second;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if ((grid[nx][ny] == 'G' || grid[nx][ny] == 'M') && dist[nx][ny] > (d+1)){
h.push({d+1, {nx, ny}});
dist[nx][ny] = d+1;
}
}
}
function<bool(int)> works = [&](ll t){
queue<pair<ll, pair<int, int>>> q;
vector<vector<ll>> di(n, vector<ll>(n, 1e9));
di[m.first][m.second] = 0;
q.push({0, m});
while (!q.empty()){
int x = q.front().second.first;
int y = q.front().second.second;
ll d = q.front().first;
q.pop();
if (di[x][y] != d) continue;
for (auto ne : dir){
int nx = x + ne.first;
int ny = y + ne.second;
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if ((grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && di[nx][ny] > (d+1) && (d+1) < s*(-t+dist[nx][ny])){
q.push({d+1, {nx, ny}});
di[nx][ny] = d+1;
}
}
}
if (di[dest.first][dest.second] == 1e9){
return false;
}
return true;
};
ll l = 0, r = n*n;
while (l < r){
ll m = (l+r+1)/2;
if (works(m)){
l = m;
}else{
r = m-1;
}
}
cout << l << endl;
}
