#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef tuple<int,int,int> iii;
const int maxN = 810;
char a[maxN][maxN];
int dist[maxN][maxN],vis[maxN][maxN];
int n,s;
int mi,mj;
int dX[] = {-1,0,0,1};
int dY[] = {0,1,-1,0};
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> s;
queue<iii> q;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> a[i][j];
dist[i][j] = INT_MAX;
if (a[i][j] == 'H'){
q.push({i,j,0});
}
else if (a[i][j] == 'M'){
mi = i; mj = j;
}
}
}
auto check1 = [&](int i,int j) -> bool {
if (
i > -1 && j > -1 &&
i < n && j < n &&
(a[i][j] == 'G' || a[i][j] == 'M') &&
dist[i][j] == INT_MAX
) return true;
return false;
};
while (!q.empty()){
int d,i,j; tie(i,j,d) = q.front();
q.pop();
if (dist[i][j] != INT_MAX) continue;
dist[i][j] = d;
for (int x = 0; x < 4; x++){
int toi = dX[x] + i,toj = dY[x] + j;
if (check1(toi,toj)){
q.push({toi,toj,d+1});
}
}
}
auto check2 = [&](int i,int j,int step,int m){
if (i > -1 && j > -1 &&
i < n && j < n && vis[i][j] == -1 &&
a[i][j] != 'T' && m + step / s < dist[i][j]
) return true;
return false;
};
auto bincheck = [&](int m) -> bool {
memset(vis,-1,sizeof(vis));
queue<iii> q;
if (check2(mi,mj,0,m)) q.push({mi,mj,0});
bool arrived = false;
while (!q.empty()){
int i,j,step; tie(i,j,step) = q.front(); q.pop();
if (vis[i][j] != -1) continue;
if (a[i][j] == 'D'){
arrived = true;
break;
}
vis[i][j] = 1;
for (int x = 0; x < 4; x++){
int toi = dX[x] + i,toj = dY[x] + j;
if (check2(toi,toj,step+1,m)){
q.push({toi,toj,step+1});
}
}
}
return arrived;
};
int l = 0,r = 1e9,ans = -1;
while (l <= r){
int m = (l+r) / 2;
if (bincheck(m)){
ans = m;
l = m+1;
}
else r = m-1;
}
cout << ans << endl;
return 0;
}
