#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct tpos
{
int i, j, t;
};
bool operator < (const tpos &a, const tpos &b)
{
if (a.i == b.i) return a.j < b.j;
return a.i < b.i;
}
char mat[801][801];
int tiempo[801][801];
//int tiempo_oso[801][801];
int iini, jini, ifin, jfin;
int n, s;
vector<tpos> abejas;
bool verifica (int i, int j)
{
if (i < 0 || j < 0 || i >= n || j >= n)
return 0;
return 1;
}
int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
void expande_abejas(queue<tpos> &abeja)
{
tpos t;
int ti, tj;
while (!abeja.empty())
{
t = abeja.front(); abeja.pop();
tiempo[t.i][t.j] = t.t;
for (int k = 0; k < 4; k++)
{
ti = t.i + di[k], tj = t.j + dj[k];
if (!verifica(ti, tj)) continue;
if (tiempo[ti][tj] != -1) continue;
if (mat[ti][tj] == 'T') continue;
abeja.push({ti, tj, t.t + 1});
}
}
}
bool sepuede(int t)
{
vector<vector<bool>>visi(n, vector<bool>(n, 0)); //llegue?
queue<tpos> mecho;
mecho.push({iini, jini, t+1});
tpos temp;
int ti, tj;
// cout << t << '\n';
int turno = 0;
visi[iini][jini] = 1;
while (!mecho.empty())
{
temp = mecho.front(); mecho.pop();
//cout << temp.i << " " << temp.j << " " <<temp.t << '\n';
/* if (t + (temp.t - t)/(s+1) > tiempo[temp.i][temp.j]) continue;
tiempo_oso[temp.i][temp.j] = temp.t;*/
int realt = (temp.t - t)/(1+s);
if (mat[temp.i][temp.j] == 'D') return 1;
for (int k = 0; k < 4; k++)
{
ti = temp.i + di[k];
tj = temp.j + dj[k];
if (!verifica(ti, tj)) continue;
if (visi[ti][tj]) continue;
if (mat[ti][tj] == 'T') continue;
if (tiempo[ti][tj] < (t + (temp.t - t + 1)/(1+s))) continue;
mecho.push({ti, tj, temp.t + 1});
visi[ti][tj] = 1;
}
}
return 0;
}
int main ()
{
cin >> n >> s;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
tiempo[i][j] = -1;
cin >> mat[i][j];
if (mat[i][j] == 'M')
{
iini = i;
jini = j;
continue;
}
if (mat[i][j] == 'H')
{
abejas.pb({i, j, 0});
tiempo[i][j] = 0;
}
if (mat[i][j] == 'D')
{
ifin = i;
jfin = j;
}
}
queue<tpos> a;
for (int i = 0, l = abejas.size(); i < l; i++)
a.push(abejas[i]);
int l = 0, r = (1<<11), resp = 0;
expande_abejas(a);
while (l <= r)
{
int mit = (l+r)>>1;
if (sepuede(mit))
{
resp = mit;
l = mit+1;
continue;
}
r = mit-1;
}
cout << resp-1;
/* for (int i = 0; i < n; i++, cout << '\n')
for (int j = 0; j < n; j++)
cout << tiempo[i][j] << " ";
cout << '\n';
sepuede(2);
for (int i = 0; i < n; i++, cout << '\n')
for (int j = 0; j < n; j++)
cout << tiempo_oso[i][j] << " ";
//cout << resp;
//sepuede(1);
*/
return 0;
}
