#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
char grid[801][801];
ll dis_b[801][801], color_b[801][801];
ll color[801][801], dis[801][801];
ll dx[4] = {0, 0, 1, -1};
ll dy[4] = {1, -1, 0, 0};
ll n, s;
pair<ll, ll> finish;
bool valid(ll i, ll j){
return (0 <= i && i < n && 0 <= j && j < n);
}
void bfs_b(queue<pair<ll, ll>> &q){
while(!q.empty()){
ll x = q.front().first, y = q.front().second;
q.pop();
for(ll i = 0; i < 4; i++){
if(valid(x + dx[i], y + dy[i]) && !color_b[x + dx[i]][y + dy[i]] &&
(grid[x + dx[i]][y + dy[i]] == 'G' || grid[x + dx[i]][y + dy[i]] == 'M')){
dis_b[x + dx[i]][y + dy[i]] = dis_b[x][y] + 1;
color_b[x + dx[i]][y + dy[i]] = 1;
q.push({x + dx[i], y + dy[i]});
}
}
}
}
bool bfs_m(ll i, ll j, ll t){
memset(color, 0, sizeof(color));
memset(dis, 0, sizeof(dis));
dis[i][j] = t;
color[i][j] = 1;
if(dis[i][j] >= dis_b[i][j] * s) return false;
queue<pair<ll, ll>> q;
q.push({i, j});
while(!q.empty()){
ll x = q.front().first, y = q.front().second;
q.pop();
for(ll i = 0; i < 4; i++){
if(valid(x + dx[i], y + dy[i]) && !color[x + dx[i]][y + dy[i]] &&
(dis[x][y] + 1 < dis_b[x + dx[i]][y + dy[i]] * s || grid[x + dx[i]][y + dy[i]] == 'D') &&
(grid[x + dx[i]][y + dy[i]] == 'G' || grid[x + dx[i]][y + dy[i]] == 'D')){
dis[x + dx[i]][y + dy[i]] = dis[x][y] + 1;
color[x + dx[i]][y + dy[i]] = 1;
q.push({x + dx[i], y + dy[i]});
}
}
}
return color[finish.first][finish.second];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>s;
if(n == 1){
cout<<-1;
return 0;
}
queue<pair<ll, ll>> b, m;
for(ll i = 0; i < n; i++){
for(ll j = 0; j < n; j++){
cin>>grid[i][j];
if(grid[i][j] == 'H'){
b.push({i, j});
color_b[i][j] = 1;
dis_b[i][j] = 0;
}else if(grid[i][j] == 'M'){
m.push({i, j});
}else if(grid[i][j] == 'D'){
finish = {i, j};
}
}
}
bfs_b(b);
if(!bfs_m(m.front().first, m.front().second, 0)){
cout<<-1;
return 0;
}
ll l = 0, r = 2e9;
ll ans = 0;
while(l <= r){
ll mid = (l + r) / 2;
if(bfs_m(m.front().first, m.front().second, s * mid)){
l = mid + 1;
ans = max(ans, mid);
}else r = mid - 1;
}
cout<<ans;
}
