#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define MAX 805
const int INF = 1e9;
char forest[MAX][MAX];
int bear[MAX][MAX];
int bees[MAX][MAX];
bool vis[MAX][MAX];
int n, s;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int mecho1, mecho2, home1, home2;
bool ok(int x, int y) {
return (x >= 1 && y >= 1 && x <= n && y <= n &&
forest[x][y] != 'T' && forest[x][y] != 'H');
}
bool reached(int x, int y) {
return (x / s < y);
}
void solve() {
cin >> n >> s;
FOR(i, 1, n) FOR(j, 1, n) {
cin >> forest[i][j];
if (forest[i][j] == 'M') {
mecho1 = i;
mecho2 = j;
}
if (forest[i][j] == 'D') {
home1 = i;
home2 = j;
}
}
queue<pair<int,int>> q;
FOR(i, 1, n) FOR(j, 1, n) {
if (forest[i][j] == 'H') {
vis[i][j] = true;
q.push({i, j});
} else bees[i][j] = INF;
}
while (!q.empty()) {
pair<int,int> cur = q.front(); q.pop();
int x = cur.first, y = cur.second;
FOR(d, 0, 3) {
int nx = x + dx[d];
int ny = y + dy[d];
if (ok(nx, ny) && !vis[nx][ny]) {
bees[nx][ny] = bees[x][y] + 1;
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
int low = 0, high = n * n + 2027, answer = 0;
while (low <= high) {
int mid = (low + high) / 2;
FOR(i, 1, n) FOR(j, 1, n) {
vis[i][j] = false;
if (i == mecho1 && j == mecho2) bear[i][j] = 0;
else bear[i][j] = INF;
}
queue<pair<int,int>> q;
q.push({mecho1, mecho2});
vis[mecho1][mecho2] = true;
if (mid >= bees[mecho1][mecho2]) q.pop();
while (!q.empty()) {
pair<int,int> cur = q.front(); q.pop();
int x = cur.first, y = cur.second;
FOR(d, 0, 3) {
int nx = x + dx[d];
int ny = y + dy[d];
if (ok(nx, ny) && reached(bear[x][y] + 1, bees[nx][ny] - mid) && !vis[nx][ny]) {
bear[nx][ny] = bear[x][y] + 1;
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
bool reach = false;
FOR(d, 0, 3) {
int nx = home1 + dx[d];
int ny = home2 + dy[d];
if (ok(nx, ny) && reached(bear[nx][ny], bees[nx][ny] - mid) && vis[nx][ny]) {
reach = true;
break;
}
}
if (reach) {
answer = mid;
low = mid + 1;
} else high = mid - 1;
}
cout << answer << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
