#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main(){
int n, s;
cin >> n >> s;
vector<string> a(n);
pi start, home;
queue<pi> q;
vvi bee(n, vi(n, 1e9));
for(int i = 0; i < n; i++){
cin >> a[i];
for(int j = 0; j < n; j++){
if(a[i][j] == 'M'){
start = {i, j};
}
else if(a[i][j] == 'D'){
home = {i, j};
}
else if(a[i][j] == 'H'){
q.push({i, j});
bee[i][j] = 0;
}
}
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
auto valid = [&](int x, int y){
return x >= 0 && x < n && y >= 0 && y < n;
};
// bee distances
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(valid(nx, ny) &&
bee[nx][ny] == 1e9 &&
(a[nx][ny] == 'G' || a[nx][ny] == 'M')){
bee[nx][ny] = bee[x][y] + 1;
q.push({nx, ny});
}
}
}
// Mecho shortest moves ignoring bees
vvi mecho(n, vi(n, 1e9));
queue<pi> q2;
mecho[start.first][start.second] = 0;
q2.push(start);
while(!q2.empty()){
auto [x, y] = q2.front();
q2.pop();
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(valid(nx, ny) &&
mecho[nx][ny] == 1e9 &&
a[nx][ny] != 'T' &&
a[nx][ny] != 'H'){
mecho[nx][ny] = mecho[x][y] + 1;
q2.push({nx, ny});
}
}
}
auto check = [&](int wait){
if(bee[start.first][start.second] <= wait) return false;
// only check cells adjacent to D
for(int i = 0; i < 4; i++){
int x = home.first + dx[i];
int y = home.second + dy[i];
if(!valid(x, y)) continue;
if(mecho[x][y] == 1e9) continue;
if(mecho[x][y] / s < bee[x][y] - wait){
return true;
}
}
return false;
};
int lo = 0, hi = n * n;
while(lo < hi){
int mid = lo + (hi - lo + 1) / 2;
if(check(mid)) lo = mid;
else hi = mid - 1;
}
if(!check(0)) cout << -1 << '\n';
else cout << lo << '\n';
}
