#include<bits/stdc++.h>
using namespace std;
#define in insert
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define Endl "\n"
#define ENDL "\n"
#define fi first
#define se second
#define be begin()
#define en end()
#define pb push_back
typedef long long ll;
typedef long double ld;
const int MOD=1e9+7;
const int MAX=2e5+1;/*
ll binpow(ll a, ll b) {
ld res = 1;
while (b > 0) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
unsigned long long power(unsigned long long x,
ll y, ll p)
{
unsigned long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
unsigned long long modInverse(unsigned long long n,
ll p)
{
return power(n, p - 2, p);
}
*/
ll n , k ;
ll dx[]={0 , 0 , 1, -1};
ll dy[]={1 , -1 , 0, 0};
char grid[805][805];
ll vis[805][805];
ll levelm[805][805];
ll levelh[805][805];
vector<pair<ll,ll>>hive;
bool valid(ll x , ll y)
{
return x>=0 && y>=0 && x<n && y<n && grid[x][y]!='H' && grid[x][y]!='T';
}
bool valid1(ll x , ll y)
{
return x>=0 && y>=0 && x<n && y<n && grid[x][y]!='T';
}
pair<ll,ll>m , d;
bool check(ll u)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
levelm[i][j]=1e18;
}
}
memset(vis , 0 ,sizeof vis );
queue< pair<ll,ll> >q;
q.push({m.fi,m.se});
vis[m.fi][m.se]=1;
levelm[m.fi][m.se]=0;
while(!q.empty())
{
pair<ll,ll>p=q.front();
q.pop();
for(int i=0;i<4;i++)
{
ll nx = p.fi + dx[i];
ll ny = p.se + dy[i];
if(!valid(nx,ny))continue;
levelm[nx][ny]=min(levelm[p.fi][p.se]+1 ,levelm[nx][ny]);
ll qe = (levelm[nx][ny] + u)/k;
if(levelh[nx][ny] <= qe)continue;
if(vis[nx][ny])continue;
vis[nx][ny] = 1;
q.push({nx , ny});
}
}
if(levelm[d.fi][d.se] != 1e18)
{
return true;
}
return false;
}
void bfs(vector<pair<ll,ll>>h)
{
queue<pair<ll,ll> >q;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
levelh[i][j]=1e18;
}
}
for(int i=0;i<h.size();i++)
{
levelh[h[i].fi][h[i].se]=0;
vis[h[i].fi][h[i].se]=1;
q.push(h[i]);
}
while(!q.empty())
{
pair<ll,ll>p=q.front();
q.pop();
for(int i=0;i<4;i++)
{
ll nx = p.fi + dx[i];
ll ny = p.se + dy[i];
if(!valid1(nx,ny))continue;
levelh[nx][ny] = min(levelh[p.fi][p.se]+1 ,levelh[nx][ny]);
if(vis[nx][ny])continue;
vis[nx][ny] = 1;
q.push({nx , ny});
}
}
}
int main()
{
fastio
//freopen("gravity.in","r",stdin);
//freopen("gravity.out","w",stdout);
cin>>n>>k;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
for(int j=0;j<s.size();j++)
{
grid[i][j]=s[j];
if(s[j]=='H')hive.pb({i,j});
else if(s[j]=='M')m={i,j};
else if(s[j]=='D')d={i,j};
}
}
bfs(hive);
memset(vis , 0 ,sizeof vis);
ll l=0;
ll r=1e18;
ll ans=-1;
while(l<=r)
{
ll mid=(l+r)/2;
if(check(mid))
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<endl;
return 0;
}
/*
5 6
0 4 0
0 3 1
0 1 1
0 2 1
1 2 1
3 4 0
*/
