#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
#define int long long
#define pi pair<int, int>
#define f first
#define s second
const int N = 805;
const int INF = 1e10;
vector<vector<char>> grid(N, vector<char>(N));
vector<vector<int>> vis(N, vector<int>(N, INF));
vector<vector<int>> v(N, vector<int>(N, INF));
vector<pi> moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<pi> bees;
pi mecho;
pi loc;
int n, m;
int steps;
bool ok(int i, int j, int val)
{
return (i >= 0 && i < n && j >= 0 && j < m && vis[i][j] > val && grid[i][j] != 'T');
}
bool ok2(int i, int j, int val)
{
return (i >= 0 && i < n && j >= 0 && j < m && v[i][j] > val && grid[i][j] != 'T');
}
void bee_bfs()
{
queue<pi> q;
for (auto p : bees)
{
vis[p.f][p.s] = 0;
q.push(p);
}
while (!q.empty())
{
auto p = q.front();
q.pop();
for (auto mv : moves)
{
int val = vis[p.f][p.s] + 1;
if (ok(p.f + mv.f, p.s + mv.s, val))
{
vis[p.f + mv.f][p.s + mv.s] = val;
q.push({p.f + mv.f, p.s + mv.s});
}
}
}
}
void mecho_bfs()
{
queue<pi> q;
v[mecho.f][mecho.s] = 0;
q.push(mecho);
while (!q.empty())
{
auto p = q.front();
q.pop();
for (auto mv : moves)
{
int val = v[p.f][p.s] + 1;
if (ok2(p.f + mv.f, p.s + mv.s, val))
{
v[p.f + mv.f][p.s + mv.s] = val;
q.push({p.f + mv.f, p.s + mv.s});
}
}
}
}
bool issoke(int t)
{
return (((v[loc.f][loc.s]) / steps) + t) < (vis[loc.f][loc.s]);
}
signed main()
{
cin >> n >> steps;
m = n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> grid[i][j];
if (grid[i][j] == 'M')
{
mecho.f = i;
mecho.s = j;
}
else if (grid[i][j] == 'H')
{
bees.push_back({i, j});
}
else if (grid[i][j] == 'D')
{
loc.f = i;
loc.s = j;
}
}
}
bee_bfs();
mecho_bfs();
if (!issoke(0))
{
cout << -1 << '\n';
return 0;
}
int l = 0;
int r = 1;
while (issoke(r))
{
r *= 2;
}
while (l + 1 < r)
{
int m = (l + r) / 2;
if (issoke(m))
{
l = m;
}
else
{
r = m;
}
}
cout << l << '\n';
}
