#include <bits/stdc++.h>
using P = std::pair<int, int>;
const int INF = 1e9;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int32_t main() {
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int N, S; std::cin >> N >> S;
std::vector<std::string> a(N);
P start, end;
std::vector<std::vector<int>> dpB(N, std::vector<int>(N, INF));
std::queue<P> qb;
for(int i = 0; i < N; i++){
std::cin >> a[i];
for(int j = 0; j < N; j++){
if(a[i][j] == 'M'){
start = P(i, j);
a[i][j] = 'G';
}else if(a[i][j] == 'D'){
end = P(i, j);
}else if(a[i][j] == 'H'){
qb.emplace(i, j);
dpB[i][j] = 0;
}
}
}
while(!qb.empty()){
P tp = qb.front(); qb.pop();
for(int i = 0; i < 4; i++){
int nx = tp.first + dx[i];
int ny = tp.second + dy[i];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if(a[nx][ny] == 'G'){
if(dpB[nx][ny] > dpB[tp.first][tp.second] + S){
dpB[nx][ny] = dpB[tp.first][tp.second] + S;
qb.emplace(nx, ny);
}
}
}
}
std::vector<std::vector<int>> dp = dpB;
auto check = [&](int delay) -> bool{
int tickStart = delay * S;
if(tickStart >= dpB[start.first][start.second]) return false;
// can only walk through regions wich tick value less
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) dp[i][j] = INF;
std::queue<P> q;
q.push(start); dp[start.first][start.second] = tickStart;
while(!q.empty()){
P tp = q.front(); q.pop();
if(tp == end) return true;
for(int i = 0; i < 4; i++){
int nx = tp.first + dx[i];
int ny = tp.second + dy[i];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if(dpB[nx][ny] <= dp[tp.first][tp.second] + 1) continue;
if(a[nx][ny] == 'G' || a[nx][ny] == 'D'){
if(dp[nx][ny] > dp[tp.first][tp.second] + 1){
dp[nx][ny] = dp[tp.first][tp.second] + 1;
q.emplace(nx, ny);
}
}
}
}
return false;
};
if(!check(0)){
std::cout << "-1\n";
return 0;
}
int l = -1, h = 1;
while(check(h)) h *= 2;
while(l < h){
int mid = l + (h - l + 1) / 2;
if(check(mid)){
l = mid;
}else{
h = mid - 1;
}
}
std::cout << l << '\n';
return 0;
}
