#include <bits/stdc++.h>
#define _FILE "TEMP"
#define ll long long
using namespace std;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
int n,s,xm,ym;
char a[807][807];
int d[807][807];
bool check(int t) {
if (t >= d[xm][ym]) return 0;
queue<pair<pair<int,int>,ll>> q;
vector<vector<bool>> f(n+7,vector<bool>(n+7,0));
q.push({{xm,ym},1ll*s*t});
f[xm][ym] = 1;
while (!q.empty()) {
int x = q.front().first.first;
int y = q.front().first.second;
ll cur = q.front().second;
q.pop();
// cerr << x << ' ' << y << ' ' << cur << '\n';
if (a[x][y] == 'D') return 1;
for (int i=0; i<4; i++) {
int u = x + dx[i];
int v = y + dy[i];
if (u >= 1 && u <= n && v >= 1 && v <= n && (a[u][v] == 'G' || a[u][v] == 'D') && !f[u][v]) {
if ((cur+1)%s != 0 && (cur+s)/s <= d[u][v]) {
f[u][v] = 1;
q.push({{u,v},cur+1});
}
else if ((cur+1)%s == 0 && (cur+1)/s < d[u][v]) {
f[u][v] = 1;
q.push({{u,v},cur+1});
}
}
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
#ifdef EMERGENCY_DEBUG
freopen(_FILE".inp","r",stdin);
freopen(_FILE".out","w",stdout);
#endif
cin >> n >> s;
queue<pair<int,int>> q;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
cin >> a[i][j];
d[i][j] = 1e9;
if (a[i][j] == 'H') {
q.push({i,j});
d[i][j] = 0;
}
if (a[i][j] == 'M') {
xm = i;
ym = j;
}
}
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i=0; i<4; i++) {
int u = x + dx[i];
int v = y + dy[i];
if (u >= 1 && u <= n && v >= 1 && v <= n && a[u][v] != 'T' && d[u][v] == 1e9) {
d[u][v] = d[x][y] + 1;
q.push({u,v});
}
}
}
int l=-1, h=n*n;
while (l < h) {
int mid = l + (h-l+1)/2;
if (check(mid)) l = mid;
else h = mid - 1;
}
cout << l;
return 0;
}
