#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;
vector<int> dr{-1, 1, 0, 0}, dc{0, 0, 1, -1};
int n, s, mid;
vector<vector<char>> a;
int x, y, xx, yy;
vector<vector<int>> dis, diss;
bool vis[801][801] = {false};
void dfs(int r, int c)
{
vis[r][c] = true;
for (int i = 0; i < 4; i++)
{
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= n || nc >= n || vis[nr][nc] || a[nr][nc] == 'T' || (dis[nr][nc] / s >= diss[nr][nc] - mid))
continue;
dfs(nr, nc);
}
}
bool check()
{
memset(vis, false, sizeof(vis));
if (mid >= diss[x][y])
return false;
dfs(x, y);
return vis[xx][yy];
}
int main()
{
cin >> n >> s;
a = vector<vector<char>>(n, vector<char>(n));
queue<pair<int, int>> node;
dis = vector<vector<int>>(n, vector<int>(n, inf));
diss = vector<vector<int>>(n, vector<int>(n, inf));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
if (a[i][j] == 'M')
{
x = i, y = j;
}
else if (a[i][j] == 'D')
{
xx = i, yy = j;
}
else if (a[i][j] == 'H')
{
node.push({i, j});
diss[i][j] = 0;
}
}
}
while (!node.empty())
{
auto cur = node.front();
node.pop();
int r = cur.first, c = cur.second;
for (int i = 0; i < 4; i++)
{
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nr >= n || nc >= n || nc < 0 || a[nr][nc] == 'T' || a[nr][nc] == 'D')
continue;
if (diss[nr][nc] > diss[r][c] + 1)
{
diss[nr][nc] = diss[r][c] + 1;
node.push({nr, nc});
}
}
}
node.push({x, y});
dis[x][y] = 0;
while (!node.empty())
{
auto cur = node.front();
node.pop();
int r = cur.first, c = cur.second;
for (int i = 0; i < 4; i++)
{
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= n || nc >= n || a[nr][nc] == 'T')
continue;
if (dis[nr][nc] > dis[r][c] + 1)
{
dis[nr][nc] = dis[r][c] + 1;
node.push({nr, nc});
}
}
}
int l = -1, r = 2 * n * n;
while (r > l + 1)
{
mid = (l + r) / 2;
if (check())
l = mid;
else
r = mid;
}
cout << l;
return 0;
}
