#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];
bool viz[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;
}
struct State {
int x, y;
int now, cnt;
};
bool check( int tt ) {
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= n; ++j ) {
viz[i][j] = false;
}
}
queue<State> q;
q.push({xs, ys, 0, 0});
viz[xs][ys] = true;
while ( !q.empty() ) {
auto [x, y, now, cnt] = q.front();
if ( x == xd && y == yd ) {
return true;
}
q.pop();
int nnow = now + 1, ncnt = cnt;
if ( nnow == s ) {
nnow = 0;
++ncnt;
}
for ( int d = 0; d < 4; ++d ) {
int nx = x + dx[d], ny = y + dy[d];
if ( !out(nx, ny) && !viz[nx][ny] ) {
if ( lim[nx][ny] > tt + ncnt ) {
q.push({nx, ny, nnow, ncnt});
viz[nx][ny] = true;
}
}
}
}
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;
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});
}
}
}
/*for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= n; ++j ) {
cout << lim[i][j] << " ";
}
cout << "\n";
}*/
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;
}
