/*
ID: c4ts0up
LANG: C++
TASK: Mecho
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define ff first
#define ss second
const int NMAX = 805;
const int INF = 1e9;
int n, s;
pair <int,int> home, mecho;
char grid[NMAX][NMAX];
int dist[NMAX][NMAX];
// hace el check a una coordenada
bool Check(int row, int col) {
return (0 <= row && row < n && 0 <= col && col < n);
}
// BFS para encontrar el tiempo requerido para que las abejas lleguen a un lugar
void EncontrarDistancias() {
queue <pair <int,int> > to;
set <pair <int,int> > seen;
for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
if (grid[i][j] == 'H') to.push({i,j}), dist[i][j] = 0;
else dist[i][j] = INF;
}
while (!to.empty()) {
pair <int,int> curr = to.front();
to.pop();
// ya lo visitamos
if (seen.count(curr)) continue;
if (grid[curr.ff][curr.ss] == 'T') {
seen.insert(curr);
continue;
}
// visitamos a todos los vecinos
if (!seen.count({curr.ff+1, curr.ss}) && Check(curr.ff+1, curr.ss)) to.push({curr.ff+1, curr.ss}), dist[curr.ff+1][curr.ss] = min(dist[curr.ff+1][curr.ss], dist[curr.ff][curr.ss]+1);
if (!seen.count({curr.ff-1, curr.ss}) && Check(curr.ff-1, curr.ss)) to.push({curr.ff-1, curr.ss}), dist[curr.ff-1][curr.ss] = min(dist[curr.ff-1][curr.ss], dist[curr.ff][curr.ss]+1);
if (!seen.count({curr.ff, curr.ss+1}) && Check(curr.ff, curr.ss+1)) to.push({curr.ff, curr.ss+1}), dist[curr.ff][curr.ss+1] = min(dist[curr.ff][curr.ss+1], dist[curr.ff][curr.ss]+1);
if (!seen.count({curr.ff, curr.ss-1}) && Check(curr.ff, curr.ss-1)) to.push({curr.ff, curr.ss-1}), dist[curr.ff][curr.ss-1] = min(dist[curr.ff][curr.ss-1], dist[curr.ff][curr.ss]+1);
seen.insert(curr);
}
}
bool BFS(int minutos) {
bool seen[NMAX][NMAX];
queue <pair <int, pair <int,int> > > to;
to.push({0, mecho});
for (int i=0; i<=n; i++) for (int j=0; j<=n; j++) seen[i][j] = false;
while (!to.empty()) {
pair <int, pair <int,int> > curr = to.front();
to.pop();
int r = curr.ss.ff;
int c = curr.ss.ss;
int pasos = curr.ff;
// ya lo visitamos, no tenemos que volver
if (seen[r][c]) continue;
// no podemos atravesarlo
if (grid[r][c] == 'T') {
seen[r][c] = true;
continue;
}
else if (grid[r][c] == 'D') return true;
// ya está infestado de abejas, o sea, bloqueado
if (minutos + (curr.ff/s) >= dist[r][c]) {
seen[r][c] = true;
continue;
}
// visitamos a todos los vecinos
if (!seen[r+1][c] && Check(r+1, c)) to.push({pasos, {r+1,c}});
if (!seen[r-1][c] && Check(r-1, c)) to.push({pasos, {r-1,c}});
if (!seen[r][c+1] && Check(r, c+1)) to.push({pasos, {r,c+1}});
if (!seen[r][c-1] && Check(r, c-1)) to.push({pasos, {r,c-1}});
seen[r][c] = true;
}
return false;
}
int main() {
/*//
freopen("", "r", stdin);
freopen("", "w", stdout);
//*/
cin >> n >> s;
for (int i=0; i<n; i++) {
string aux;
cin >> aux;
for (int j=0; j<n; j++) {
grid[i][j] = aux[j];
if (grid[i][j] == 'M') mecho = {i,j};
else if (grid[i][j] == 'D') home = {i,j};
}
}
EncontrarDistancias();
if (!BFS(0)) {
cout << -1 << endl;
exit(0);
}
int lb = 0, ub = 1e6, mid;
while (lb <= ub) {
mid = (lb+ub)/2;
if (BFS(mid)) lb = mid+1;
else ub = mid-1;
}
//cerr << "lb = " << lb << "; ub = " << ub << "; mid = " << mid << endl;
cout << ub-1 << endl;
return 0;
}
