//made by Nguyễn Hồng Nam
#include <bits/stdc++.h>
using namespace std;
#define ll int
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pll pair<ll,ll>
#define fi first
#define se second
const ll mod = 1e9 + 7,inf = 1e9,mxn = 805;
string s[mxn];
ll n,step,ans = inf,bear[mxn][mxn],bee[mxn][mxn],row[4] = {-1,0,0,1},col[4] = {0,-1,1,0},inf2;
pll start,en;
bool mark[mxn][mxn];
void minz(ll &a,ll b)
{
if(a > b ) a = b;
}
bool check_bee(ll a,ll b)
{
if(a >= 0 && a < n && b >= 0 && b < n && s[a][b] != 'T' && s[a][b] != 'D' && s[a][b] != 'H') return true;
return 0;
}
bool check_bear(ll a,ll b)
{
if(a >= 0 && a < n && b >= 0 && b < n && s[a][b] != 'T' && s[a][b] != 'H' && mark[a][b] == 0) return true;
return 0;
}
void bfs_hive(ll i,ll j)
{
if(bee[i][j] == 0) return;
memset(mark,false,sizeof mark);
bee[i][j] = 0;
mark[i][j] = 1;
queue<pll> q;
q.push({i,j});
while(!q.empty())
{
pll u = q.front();
q.pop();
mark[u.fi][u.se] = 1;
for(ll k = 0; k < 4; k++)
{
ll a = u.fi + row[k],b = u.se + col[k];
if(check_bee(a,b) && bee[u.fi][u.se] + 1 < bee[a][b])
{
bee[a][b] = bee[u.fi][u.se] + 1;
mark[a][b] = 1;
q.push({a,b});
}
}
}
}
void bfs(ll i,ll j )
{
memset(mark,0,sizeof mark);
mark[i][j] = 1;
queue<pll> q;
q.push({i,j});
bear[i][j] = 0;
while(!q.empty())
{
pll u = q.front();
mark[u.fi][u.se] = 1;
q.pop();
for(ll k = 0; k < 4; k++)
{
ll a = u.fi + row[k],b = u.se + col[k];
if(check_bear(a,b))
{
mark[a][b] = 1;
bear[a][b] = bear[u.fi][u.se] + 1;
q.push({a,b});
//if(a == en.fi && b == en.se) return;
}
}
}
}
bool f(ll x)
{
memset(mark,0,sizeof mark);
mark[start.fi][start.se] = 1;
queue<pair<pll,ll>>q;
q.push({start,0});
while(!q.empty())
{
auto u = q.front();
q.pop();
mark[u.fi.fi][u.fi.se] = 1;
for(ll i = 0; i < 4; i++)
{
ll a = u.fi.fi + row[i],b = u.fi.se + col[i];
if(mark[a][b] == 0 && a >= 0 && a < n && b >= 0 && b < n && s[a][b] != 'T' && s[a][b] != 'H' && (x + ((u.se + 1) / step)) < bee[a][b])
{
mark[a][b] = 1;
q.push({{a,b},u.se + 1});
}
}
}
if(mark[en.fi][en.se] == 1) return 1;
return 0;
}
int main()
{
#define taskname "mecho"
if (fopen(taskname".inp", "r"))
{
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin >> n >> step;
string x;
cin >> x;
for(ll i = 0; i < n; i++)
{
s[i].resize(n);
for(ll j = 0;j < n;j++) s[i][j] = x[i * n + j];
for(ll j = 0; j < n; j++)
{
if(s[i][j] == 'M') start = {i,j};
else if(s[i][j] == 'D') en = {i,j};
}
}
memset(bee,60,sizeof bee);
inf2 = bee[0][0];
for(ll i = 0; i < n; i++)
{
for(ll j = 0; j < n; j++) if(s[i][j] == 'H') bfs_hive(i,j);
}
bfs(start.fi,start.se);
ll lf = 0,rt = inf - 1;
while(lf <= rt)
{
ll mid = (lf + rt)/2;
if(f(mid))
{
ans = mid;
lf = mid + 1;
}
else rt = mid - 1;
}
// for(ll i = 0; i < n; i++)
// {
// for(ll j = 0; j < n; j++)
// {
// if(bee[i][j] != inf2) cout << bee[i][j] << ' ';
// else cout << "-1 ";
// }
// cout << '\n';
// }
// for(ll i = 0; i < n; i++)
// {
// for(ll j = 0; j < n; j++)
// {
// if(bee[i][j] != inf2) cout << bear[i][j] << ' ';
// else cout << "-1 ";
// }
// cout << '\n';
// }
if(ans == inf) cout << "-1\n";
else cout << ans << '\n';
return 0;
}
