#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) begin(x), end(x)
#define pb push_back
int N, S;
char A[800][800];
int d[800][800], D[800][800];
pii M, P;
int ans = -1;
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
bool invalid(int r, int c){
if(r<0 or r>=N or c<0 or c>=N) return true;
if(A[r][c] == 'T') return true;
return false;
}
bool check(int k){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) d[i][j] = 1e9;
}
queue<pii> q, qn;
q.push(M);
int tt = 0;
d[M.first][M.second] = 0;
bool found = false;
for(int x=0; x<N; x++){
while(!q.empty()){
auto p = q.front(); q.pop();
int r = p.first, c = p.second;
if(d[r][c] == (tt+1)*S){
if(D[r][c]>k+tt+1){
qn.push({r, c});
}
continue;
}
for(int i=0; i<4; i++){
int nr = r+dr[i], nc = c+dc[i];
if(invalid(nr, nc)) continue;
if(d[nr][nc] != 1e9) continue;
d[nr][nc] = d[r][c]+1;
q.push({nr, nc});
if(P == pii(nr, nc)) found = true;
}
}
if(found) break;
q = qn;
qn = queue<pii>();
tt++;
}
return found;
}
void solve(){
int L = 1, R = N;
while(L <= R){
int mid = (L+R)/2;
if(check(mid)){
ans = mid;
L=mid+1;
}
else R=mid-1;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> S;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin >> A[i][j];
if(A[i][j] == 'M') M = {i, j};
if(A[i][j] == 'D') P = {i, j};
d[i][j] = D[i][j] = 1e9;
}
}
queue<pii> Q;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(A[i][j] == 'H'){
Q.push({i, j});
D[i][j] = 0;
}
}
}
while(!Q.empty()){
auto p = Q.front(); Q.pop();
int r = p.first, c = p.second;
for(int i=0; i<4; i++){
int nr = r+dr[i], nc = c+dc[i];
if(invalid(nr, nc)) continue;
if(A[nr][nc] == 'D') continue;
if(D[nr][nc] != 1e9) continue;
D[nr][nc] = D[r][c]+1;
Q.push({nr, nc});
}
}
solve();
cout << ans;
}
