#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 805;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
int n, s;
char c[N][N];
pair<int, int> hive, house, bear;
int mecho[N][N], bee[N][N];
bool check(int time)
{
memset(mecho, -1, sizeof(mecho));
mecho[bear.fi][bear.se] = 0;
if(bee[bear.fi][bear.se] <= time) return false;
queue<pair<int, int>> p;
p.push(bear);
while(p.size())
{
int u = p.front().fi;
int v = p.front().se;
p.pop();
for(int e = 0; e < 4; e ++)
{
int nu = u + dx[e];
int nv = v + dy[e];
if(nu < 1 || nu > n) continue;
if(nv < 1 || nv > n) continue;
if(mecho[nu][nv] == -1 && c[nu][nv] != 'T')
{
if((mecho[u][v] + 1)/s + time < bee[nu][nv])
{
mecho[nu][nv] = mecho[u][v] + 1;
p.push({nu, nv});
}
}
}
}
for(int e = 0; e < 4; e ++)
{
if(house.fi + dx[e] < 1 || house.fi + dx[e] > n) continue;
if(house.se + dy[e] < 1 || house.se + dy[e] > n) continue;
if(c[house.fi + dx[e]][house.se + dy[e]] == 'T') continue;
if(c[house.fi + dx[e]][house.se + dy[e]] == 'H') continue;
if(mecho[house.fi + dx[e]][house.se + dy[e]] != -1) return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
{
cin >> c[i][j];
if(c[i][j] == 'M')
bear = {i, j};
if(c[i][j] == 'D')
house = {i, j};
}
memset(bee, -1, sizeof(bee));
queue<pair<int, int>> q;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++){
if(c[i][j] == 'H')
{
bee[i][j] = 0;
q.push({i, j});
}
}
while(q.size())
{
int u = q.front().fi;
int v = q.front().se;
q.pop();
for(int e = 0; e < 4; e ++)
{
int nu = u + dx[e];
int nv = v + dy[e];
if(nu < 1 || nu > n) continue;
if(nv < 1 || nv > n) continue;
if(bee[nu][nv] == -1 && c[nu][nv] != 'T')
{
bee[nu][nv] = bee[u][v] + 1;
q.push({nu, nv});
}
}
}
int l = 0, r = 1e9, ans = -1;
while(l <= r)
{
int mid = (l + r) / 2;
if(check(mid))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout << ans;
}
