#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 810;
char forest[N][N];
int near_bee[N][N];
int bhi, bhj, bsi, bsj;
ll n, s;
bool can_go_bear(int i, int j)
{
return 0 <= i && i < n && 0 <= j && j < n
&& forest[i][j] != 'T';
}
bool can_go_bee(int i, int j)
{
return 0 <= i && i < n && 0 <= j && j < n
&& forest[i][j] != 'T' && forest[i][j] != 'D';
}
void bfs_bee()
{
queue<pii> q;
memset(near_bee, -1, sizeof(near_bee));
Loop (i,0,n) Loop (j,0,n) {
if (forest[i][j] == 'H') {
near_bee[i][j] = 0;
q.push({i, j});
}
}
while (q.size()) {
auto [i, j] = q.front();
q.pop();
int d = near_bee[i][j];
for (auto [x_, y_] : {pii{0,1}, {0,-1}, {1,0}, {-1,0}}) {
int x = i+x_, y = j+y_;
if (!can_go_bee(x, y))
continue;
if (near_bee[x][y] != -1)
continue;
near_bee[x][y] = d+1;
q.push({x, y});
}
}
}
void find_bear()
{
Loop (i,0,n) Loop (j,0,n) {
if (forest[i][j] == 'D') {
bhi = i;
bhj = j;
}
if (forest[i][j] == 'M') {
bsi = i;
bsj = j;
}
}
}
bool bfs_bear(int wait)
{
if (wait >= near_bee[bsi][bsj])
return 0;
static ll dis[N][N];
memset(dis, -1, sizeof(dis));
queue<pii> q;
q.push({bsi, bsj});
dis[bsi][bsj] = (ll)wait * s;
while (q.size()) {
auto [i, j] = q.front();
q.pop();
ll d = dis[i][j];
for (auto [x_, y_] : {pii{0,1}, {0,-1}, {1,0}, {-1,0}}) {
int x = i+x_, y = j+y_;
if (!can_go_bear(x, y))
continue;
if (near_bee[x][y] != -1
&& near_bee[x][y] <= (d+1)/s)
continue;
if (dis[x][y] != -1)
continue;
dis[x][y] = d+1;
q.push({x, y});
}
}
return dis[bhi][bhj] != -1;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> s;
Loop (i,0,n)
cin >> forest[i];
bfs_bee();
find_bear();
int l = -1, r = near_bee[bsi][bsj]-1;
while (l < r) {
int mid = (l+r+1)/2;
if (bfs_bear(mid))
l = mid;
else
r = mid-1;
}
cout << l << '\n';
}
