#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
using namespace std;
const int N = 5 + 1e5;
const int inf = 7 + 1e9;
int n, len, s_x, s_y, t_x, t_y;
vector <vector <int>> a, h;
int dr[] = {-1, 0, 0, 1};
int dc[] = {0, -1, 1, 0};
int check(int lim) {
vector <vector <int>> f(n + 1, vector <int>(n + 1, inf));
queue <II> q;
if (h[s_x][s_y] <= lim * len)
return 0;
q.push({s_x, s_y});
f[s_x][s_y] = lim * len;
while (!q.empty()) {
int x = q.front().st, y = q.front().nd;
q.pop();
for (int i = 0; i < 4; i ++) {
int u = x + dr[i], v = y + dc[i];
if (u < 1 || u > n || v < 1 || v > n || a[u][v] || f[u][v] <= f[x][y] + 1 || h[u][v] <= f[x][y] + 1)
continue;
if (u == t_x && v == t_y)
return 1;
q.push({u, v});
f[u][v] = f[x][y] + 1;
}
}
return 0;
}
int main() {
#define TASKNAME ""
ios_base :: sync_with_stdio (0);
cin.tie (0);
if ( fopen( TASKNAME".inp", "r" ) ) {
freopen (TASKNAME".inp", "r", stdin);
freopen (TASKNAME".out", "w", stdout);
}
queue <II> q;
cin >> n >> len;
a.assign(n + 1, vector <int>(n + 1, 0));
h.assign(n + 1, vector <int>(n + 1, inf));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
char c;
cin >> c;
if (c == 'T')
a[i][j] = 1;
else if (c == 'M') {
s_x = i;
s_y = j;
}
else if (c == 'D') {
t_x = i;
t_y = j;
}
else if (c == 'H') {
a[i][j] = 1;
q.push({i, j});
h[i][j] = 0;
}
}
while (!q.empty()) {
int x = q.front().st, y = q.front().nd;
q.pop();
for (int i = 0; i < 4; i++) {
int u = x + dr[i], v = y + dc[i];
if (u < 1 || u > n || v < 1 || v > n || a[u][v] || h[u][v] <= h[x][y] + len || (u == t_x && v == t_y))
continue;
q.push({u, v});
h[u][v] = h[x][y] + len;
}
}
int lo = -1, hi = n * n + 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (check(mid))
lo = mid;
else
hi = mid - 1;
}
cout << lo;
return 0;
}
