#include <bits/stdc++.h>
#define ff first
#define ss second
#define cont continue;
#define sz size()
#define pb push
using namespace std;
typedef long long ll;
const int N = 950;
int tr[4] = {1, -1, 0, 0};
int rt[4] = {0, 0, 1, -1};
void solve();
char a[N][N];
int dis[N][N], dis2[N][N];
int vis[N][N];
int a1,a2, a3, a4, jogap = -1, n, s;
queue < pair<int,int> > q;
bool barla (int x) {
memset (vis, 0, sizeof (vis));
memset (dis2, 0, sizeof (dis2));
while (!q.empty()) q.pop();
q.push({a1, a2});
vis[a1][a2] = 1;
if (x >= dis[a1][a2]) return 0;
dis2[a1][a2] = 0;
while (!q.empty()) {
int b1 = q.front().ff;
int b2 = q.front().ss;
q.pop();
for (int i = 0; i < 4; ++i) {
int c1 = b1 + tr[i];
int c2 = b2 + rt[i];
if (c1 < 0 or c2 < 0 or c1 >= n or c2 >= n or a[c1][c2] == 'T' or a[c1][c2] == 'H') continue;
if (vis[c1][c2]) continue;
int kl = ceil((dis2[b1][b2] + 1) / (double) s) + x;
int jp = ceil (dis2[b1][b2] / (double) s) + x;
if (dis[b1][b2] == jp) {
if (kl != jp) continue;
}
if (kl <= dis[c1][c2]) {
dis2[c1][c2] = dis2[b1][b2] + 1;
q.push({c1,c2});
vis[c1][c2] = 1;
if (a[c1][c2] == 'D') return 1;
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin >> n >> s;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
dis[i][j] = 1e9;
cin >> a[i][j];
if (a[i][j] == 'M') {
a1 = i;
a[i][j] = 'G';
a2 = j;
}
else if (a[i][j] == 'D') {
a3 = i;
a4 = j;
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i][j] == 'H') {
q.push ({i, j});
dis[i][j] = 0;
vis[i][j] = 1;
}
}
}
while (!q.empty()) {
int b1 = q.front().ff;
int b2 = q.front().ss;
q.pop();
for (int i = 0; i < 4; ++i) {
int c1 = b1 + tr[i];
int c2 = b2 + rt[i];
if (c1 < 0 or c2 < 0 or c1 >= n or c2 >= n or a[c1][c2] == 'T' or a[c1][c2] == 'D' or a[c1][c2] == 'H') continue;
if (vis[c1][c2]) continue;
dis[c1][c2] = dis[b1][b2] + 1;
vis[c1][c2] = 1;
q.push({c1, c2});
}
}
int l = 0, r = 850 * 850;
while (l <= r) {
int md = (l + r) / 2;
if (barla(md)) {
l = md + 1;
jogap = md;
}
else r = md - 1;
}
cout << jogap;
return 0;
}
