#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
const int MXN = 8e2 + 5;
int A[4] = {0, 0, 1, -1};
int B[4] = {1, -1, 0, 0};
int n, s;
string arr[MXN];
vector<vector<int>> bfs(vector<array<int, 2>> st, int bee = 0)
{
vector<vector<int>> d(n, vector<int>(n, inf));
queue<array<int, 2>> q;
for (auto &[x, y] : st) q.push({x, y}), d[x][y] = 0;
while (!q.empty())
{
int x = q.front()[0], y = q.front()[1];
q.pop();
for (int k = 0; k < 4; k++)
{
int x1 = x + A[k], y1 = y + B[k];
if (min(x1, y1) < 0 || max(x1, y1) >= n || arr[x1][y1] == 'T' || d[x1][y1] <= d[x][y] + 1) continue;
if (bee && arr[x1][y1] == 'D') continue;
if (!bee && arr[x1][y1] == 'H') continue;
d[x1][y1] = d[x][y] + 1;
q.push({x1, y1});
}
}
return d;
}
void _()
{
cin >> n >> s;
for (int i = 0; i < n; i++) cin >> arr[i];
array<int, 2> M, D;
vector<array<int, 2>> H;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (arr[i][j] == 'M') M = {i, j};
if (arr[i][j] == 'H') H.push_back({i, j});
if (arr[i][j] == 'D') D = {i, j};
}
}
auto hd = bfs(H, 1);
int l = -1, r = hd[M[0]][M[1]] - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
vector<vector<int>> d(n, vector<int>(n, inf));
queue<array<int, 2>> q;
d[M[0]][M[1]] = 0;
q.push(M);
while (!q.empty())
{
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int x1 = x + A[k], y1 = y + B[k];
if (min(x1, y1) < 0 || max(x1, y1) >= n || arr[x1][y1] == 'T' || d[x1][y1] <= d[x][y] + 1) continue;
if ((d[x][y] + 1) / s + mid >= hd[x1][y1]) continue;
d[x1][y1] = d[x][y] + 1;
q.push({x1, y1});
}
}
if (d[D[0]][D[1]] != inf) l = mid;
else r = mid - 1;
}
cout << l << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) _();
}
