#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 8e2;
const int INF = 2e9;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
string T[1 + MAXN];
int lim[1 + MAXN][1 + MAXN];
int dist[1 + MAXN][1 + MAXN];
int n, s, xs, ys, xd, yd;
bool out( int x, int y ) {
return 1 > x || 1 > y || n < x || n < y;
}
bool check( int tt ) {
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= n; ++j ) {
dist[i][j] = INF;
}
}
queue<pair<int, int>> q;
q.push({xs, ys});
dist[xs][ys] = 0;
while ( !q.empty() ) {
auto [x, y] = q.front();
if ( x == xd && y == yd ) {
return true;
}
q.pop();
int nd = (dist[x][y] + 1) / s + ((dist[x][y] + 1) % s != 0);
for ( int d = 0; d < 4; ++d ) {
int nx = x + dx[d], ny = y + dy[d];
if ( !out(nx, ny) && lim[nx][ny] >= tt + nd && dist[nx][ny] == INF ) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
queue<pair<int, int>> q;
for ( int i = 1; i <= n; ++i ) {
cin >> T[i];
T[i] = '#' + T[i];
for ( int j = 1; j <= n; ++j ) {
lim[i][j] = INF;
dist[i][j] = INF;
if ( T[i][j] == 'H' ) {
q.push({i, j});
lim[i][j] = 0;
} else if ( T[i][j] == 'T' ) {
lim[i][j] = 0;
} else if ( T[i][j] == 'M' ) {
xs = i, ys = j;
} else if ( T[i][j] == 'D' ) {
xd = i, yd = j;
}
}
}
while ( !q.empty() ) {
auto [i, j] = q.front();
q.pop();
for ( int d = 0; d < 4; ++d ) {
int ni = i + dx[d], nj = j + dy[d];
if ( !out(ni, nj) && lim[ni][nj] == INF ) {
lim[ni][nj] = lim[i][j] + 1;
q.push({ni, nj});
}
}
}
int l = 0, r = lim[xs][ys];
while ( r - l > 1 ) {
int mid = (l + r) / 2;
if ( check(mid) ) {
l = mid;
} else {
r = mid;
}
}
if ( !check(0) ) {
cout << "-1\n";
return 0;
}
cout << (check(r) ? r : l) << "\n";
return 0;
}
